Colin A. Percival (born c. 1980) is a Canadian computer scientist and computer security researcher. He completed his undergraduate education at Simon Fraser University and a doctorate at the University of Oxford. While at university he joined the FreeBSD project, and achieved some notoriety for discovering a security weakness in Intel's hyper-threading technology. Besides his work in delta compression and the introduction of memory-hard functions, he is also known for developing the Tarsnap online backup service, which became his full-time job.

Colin Percival
Percival in 2019
Born
NationalityCanadian
Alma materUniversity of Oxford
OccupationComputer scientist
Years active1998–present
Known forComputer security
Notable work
Websitewww.daemonology.net

Education

edit

Percival began taking mathematics courses at Simon Fraser University (SFU) at age 13, as a student at Burnaby Central Secondary School.[1] He graduated from Burnaby Central and officially enrolled at SFU in 1998. At SFU he studied number theory under Peter Borwein, and competed in the William Lowell Putnam Mathematical Competition, placing in the top 15 in 1998[2] and as a Putnam Fellow (in the top six) in 1999.[3] From 1998 to 2000 he ran the PiHex project, organizing contributors from all over the world to help calculate specific bits of pi. Percival graduated from SFU in 2001 and was awarded a Commonwealth Scholarship to the University of Oxford.[1]

In Oxford, Percival set out to do research in distributed computing, building on his experience with PiHex. When a serious illness in 2003 interrupted this work for months, he turned his attention to the problem of building a software update system for the FreeBSD operating system. At the time, FreeBSD updates were distributed only as source code patches, making it difficult to keep systems updated. After a commenter on a mailing list suggested using xdelta to reduce the size of the files to be transferred, Percival began working on a more efficient delta compression algorithm. This new algorithm, called bsdiff, became the new focus of his doctoral research, and later a widely used standard, and his freebsd-update became a part of FreeBSD.[4] In 2004 he contributed portsnap, which uses bsdiff to distribute snapshots of the FreeBSD ports tree.

His 2006 doctoral thesis, supervised by William F. McColl and Richard P. Brent,[5] is called "Matching with Mismatches and Assorted Applications".[6] It describes further improvements to the compression of bsdiff.[7]

Career

edit

After joining the FreeBSD Security Team in 2004, Percival analyzed the behaviour of hyper-threading as then implemented on Intel's Pentium 4 CPUs. He discovered a security flaw that would allow a malicious thread to use a timing-based side-channel attack to steal secret data from another thread executing on the same processor core and sharing its cache. Some months after reporting the problem to Intel and operating system vendors, with suggestions on how to mitigate it in system software, he made the details public in May 2005.[8] Having finished his thesis, he returned to SFU as a visiting researcher.[9] He went on to serve as the FreeBSD Security Officer, from August 2005 to May 2012. He was also elected to the FreeBSD Core Team, for the 2010–2012 term.[10]

In 2008 he released the client for Tarsnap, his encrypted online backup service. He had already been trying for some two years to get FreeBSD running on the Amazon EC2 platform, and he increased these efforts. Building disk images himself, debugging kernel crashes, and coordinating with people at both Amazon and FreeBSD, he eventually overcame the technical obstacles, and Amazon announced official support for FreeBSD on EC2 in November 2012.[11] Percival has continued to support FreeBSD on EC2, and in 2019 he was recognized as an AWS Community Hero for his work and enthusiasm.[12]

In 2009 Percival uncovered a fatal flaw in AWS' use of cryptographic signatures used to authenticate EC2, SimpleDB, SQS, and S3 REST APIs.[13] The same year, while working to add passphrase protection to Tarsnap keys, he became dissatisfied with existing key derivation functions. Drawing on his experience in distributed computing, Percival modeled an attacker using specialized hardware to massively parallelize a brute-force search for the passphrase. He concluded that the key derivation functions in use were vulnerable to such an attack, and sought to make these attacks cost-prohibitive by designing an algorithm that must use an amount of memory nearly proportional to its run time. He defined memory-hard functions in these terms, and presented scrypt as a specific example, which he used as the key derivation function for Tarsnap. Memory-hard functions have since become an active area of research in cryptography, and scrypt is used as the basis of proof of work in Litecoin[14] and some other cryptocurrencies.

Since 2020 he is part of FreeBSD's primary release engineering team,[15] and he was promoted to Lead Release Engineer on November 17, 2023.[16]

Having left academia after his doctorate, Percival has only a few published papers. He has collaborated with mathematicians such as Peter Borwein and Richard P. Brent, giving him an Erdős number of 3. In the past he has announced new work on a blog he has maintained since 2005, then presented his results at BSD conferences.

Personal life

edit

Percival has Type-I diabetes.[17]

References

edit
  1. ^ a b Thorbes, Carol (June 14, 2001). "Math grad heads to Oxford". Simon Fraser University News. Vol. 21, no. 4. Retrieved June 5, 2021.
  2. ^ "1998 Putnam Competition Winners". The Putnam Archive. Retrieved June 7, 2021.
  3. ^ "1999 Putnam Competition Winners". The Putnam Archive. Retrieved June 7, 2021.
  4. ^ freebsd-update(8) – FreeBSD System Manager's Manual
  5. ^ Colin Percival at the Mathematics Genealogy Project
  6. ^ Percival, Collin (2006). Matching with Mismatches and Assorted Applications (PhD thesis). Wadham College, University of Oxford. OCLC 70990554.
  7. ^ Salomon, David; Motta, Giovanni (November 9, 2009). "11.14 File Differencing". Handbook of Data Compression. Springer. pp. 1178–1180. ISBN 978-1-84882-902-2.
  8. ^ LeMay, Renai (May 27, 2005). "Vendors 'slow to fix' hyperthreading flaw". ZDNet. Retrieved June 6, 2021.
  9. ^ Lucas, Michael W. (July 21, 2005). "Information Security with Colin Percival". ONLamp.com. O'Reilly Media. Archived from the original on January 21, 2018. Retrieved June 7, 2021.
  10. ^ Paeps, Philip (July 14, 2010). "[FreeBSD-Announce] New FreeBSD core team elected". FreeBSD Mail Archives. Retrieved June 7, 2021.
  11. ^ Barr, Jeff (November 23, 2012). "AWS Marketplace – Additional EC2 Operating System Support (FreeBSD, Debian, CentOS)". AWS News Blog. Amazon. Retrieved June 7, 2021.
  12. ^ "Colin Percival". AWS Developer Center. Amazon. 2019. Retrieved June 7, 2021.
  13. ^ Lawson, Nate (May 20, 2009). "Amazon web services signature vulnerability". rdist.root.org. Archived from the original on July 5, 2015.
  14. ^ Alwen, Joël; Serbinenko, Vladimir (November 4, 2014). "High Parallel Complexity Graphs and Memory-Hard Functions". Retrieved June 7, 2021.
  15. ^ "Release Engineering Information". The FreeBSD Project. Retrieved September 9, 2021.
  16. ^ "FreeBSD News Flash". The FreeBSD Project. Retrieved November 19, 2023.
  17. ^ Colin Percival [@cperciva] (July 13, 2021). "If I were in the USA, I would have been too concerned about health care costs -- I'm a type 1 diabetic -- and having a job offer from Google (even a very mediocre one) satisfied me that I'd do fine even if the startup thing didn't work out" (Tweet). Archived from the original on July 15, 2021 – via Twitter.