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 FreeBSDoperating 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
After joining the FreeBSD Security Team in 2004, Percival analyzed the behaviour of hyper-threading as then implemented on Intel's Pentium 4CPUs. 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 S3REST 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.
^Percival, Collin (2006). Matching with Mismatches and Assorted Applications (PhD thesis). Wadham College, University of Oxford. OCLC70990554.
^Salomon, David; Motta, Giovanni (November 9, 2009). "11.14 File Differencing". Handbook of Data Compression. Springer. pp. 1178–1180. ISBN978-1-84882-902-2.
