Colin Percival

Last updated
Colin Percival
Colin Percival 2019.jpg
Born
Burnaby, British Columbia, Canada
NationalityCanadian
Alma mater University of Oxford
Occupation Computer scientist
Years active1998–present
Known for Computer security
Notable work
Website www.daemonology.net

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.

Contents

Education

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

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

Percival has Type-I diabetes. [17]

Related Research Articles

<span class="mw-page-title-main">Hyper-threading</span> Proprietary simultaneous multithreading implementation by Intel

Hyper-threading is Intel's proprietary simultaneous multithreading (SMT) implementation used to improve parallelization of computations performed on x86 microprocessors. It was introduced on Xeon server processors in February 2002 and on Pentium 4 desktop processors in November 2002. Since then, Intel has included this technology in Itanium, Atom, and Core 'i' Series CPUs, among others.

A passphrase is a sequence of words or other text used to control access to a computer system, program or data. It is similar to a password in usage, but a passphrase is generally longer for added security. Passphrases are often used to control both access to, and the operation of, cryptographic programs and systems, especially those that derive an encryption key from a passphrase. The origin of the term is by analogy with password. The modern concept of passphrases is believed to have been invented by Sigmund N. Porter in 1982.

Delta encoding is a way of storing or transmitting data in the form of differences (deltas) between sequential data rather than complete files; more generally this is known as data differencing. Delta encoding is sometimes called delta compression, particularly where archival histories of changes are required.

The C standard library or libc is the standard library for the C programming language, as specified in the ISO C standard. Starting from the original ANSI C standard, it was developed at the same time as the C library POSIX specification, which is a superset of it. Since ANSI C was adopted by the International Organization for Standardization, the C standard library is also called the ISO C library.

7z is a compressed archive file format that supports several different data compression, encryption and pre-processing algorithms. The 7z format initially appeared as implemented by the 7-Zip archiver. The 7-Zip program is publicly available under the terms of the GNU Lesser General Public License. The LZMA SDK 4.62 was placed in the public domain in December 2008. The latest stable version of 7-Zip and LZMA SDK is version 22.01.

<span class="mw-page-title-main">Matthew Dillon</span> American software engineer (born 1966)

Matthew Dillon is an American software engineer known for Amiga software, contributions to FreeBSD and for starting and leading the DragonFly BSD project since 2003.

<span class="mw-page-title-main">Key derivation function</span> Function that derives secret keys from a secret value

In cryptography, a key derivation function (KDF) is a cryptographic algorithm that derives one or more secret keys from a secret value such as a master key, a password, or a passphrase using a pseudorandom function. KDFs can be used to stretch keys into longer keys or to obtain keys of a required format, such as converting a group element that is the result of a Diffie–Hellman key exchange into a symmetric key for use with AES. Keyed cryptographic hash functions are popular examples of pseudorandom functions used for key derivation.

<span class="mw-page-title-main">Amazon Web Services</span> On-demand cloud computing company

Amazon Web Services, Inc. (AWS) is a subsidiary of Amazon that provides on-demand cloud computing platforms and APIs to individuals, companies, and governments, on a metered, pay-as-you-go basis. Clients will often use this in combination with autoscaling. These cloud computing web services provide various services related to networking, compute, storage, middleware, IoT and other processing capacity, as well as software tools via AWS server farms. This frees clients from managing, scaling, and patching hardware and operating systems. One of the foundational services is Amazon Elastic Compute Cloud (EC2), which allows users to have at their disposal a virtual cluster of computers, with extremely high availability, which can be interacted with over the internet via REST APIs, a CLI or the AWS console. AWS's virtual computers emulate most of the attributes of a real computer, including hardware central processing units (CPUs) and graphics processing units (GPUs) for processing; local/RAM memory; Hard-disk(HDD)/SSD storage; a choice of operating systems; networking; and pre-loaded application software such as web servers, databases, and customer relationship management (CRM).

<span class="mw-page-title-main">FreeRTOS</span> Real-time operating system

FreeRTOS is a real-time operating system kernel for embedded devices that has been ported to 35 microcontroller platforms. It is distributed under the MIT License.

In cryptography, key stretching techniques are used to make a possibly weak key, typically a password or passphrase, more secure against a brute-force attack by increasing the resources it takes to test each possible key. Passwords or passphrases created by humans are often short or predictable enough to allow password cracking, and key stretching is intended to make such attacks more difficult by complicating a basic step of trying a single password candidate. Key stretching also improves security in some real-world applications where the key length has been constrained, by mimicking a longer key length from the perspective of a brute-force attacker.

<span class="mw-page-title-main">FreeBSD</span> Free and open-source Unix-like operating system

FreeBSD is a free and open-source Unix-like operating system descended from the Berkeley Software Distribution (BSD). The first version of FreeBSD was released in 1993 developed from 386BSD and the current version runs on x86, ARM, PowerPC and RISC-V processors. The project is supported and promoted by the FreeBSD Foundation.

<span class="mw-page-title-main">Amazon Elastic Compute Cloud</span> Cloud computing platform

Amazon Elastic Compute Cloud (EC2) is a part of Amazon.com's cloud-computing platform, Amazon Web Services (AWS), that allows users to rent virtual computers on which to run their own computer applications. EC2 encourages scalable deployment of applications by providing a web service through which a user can boot an Amazon Machine Image (AMI) to configure a virtual machine, which Amazon calls an "instance", containing any software desired. A user can create, launch, and terminate server-instances as needed, paying by the second for active servers – hence the term "elastic". EC2 provides users with control over the geographical location of instances that allows for latency optimization and high levels of redundancy. In November 2010, Amazon switched its own retail website platform to EC2 and AWS.

bcrypt is a password-hashing function designed by Niels Provos and David Mazières, based on the Blowfish cipher and presented at USENIX in 1999. Besides incorporating a salt to protect against rainbow table attacks, bcrypt is an adaptive function: over time, the iteration count can be increased to make it slower, so it remains resistant to brute-force search attacks even with increasing computation power.

An Amazon Machine Image (AMI) is a special type of virtual appliance that is used to create a virtual machine within the Amazon Elastic Compute Cloud ("EC2"). It serves as the basic unit of deployment for services delivered using EC2.

<span class="mw-page-title-main">Amazon Virtual Private Cloud</span> Cloud-based service

Amazon Virtual Private Cloud (VPC) is a commercial cloud computing service that provides a virtual private cloud, by provisioning a logically isolated section of Amazon Web Services (AWS) Cloud. Enterprise customers can access the Amazon Elastic Compute Cloud (EC2) over an IPsec based virtual private network. Unlike traditional EC2 instances which are allocated internal and external IP numbers by Amazon, the customer can assign IP numbers of their choosing from one or more subnets.

RDRAND is an instruction for returning random numbers from an Intel on-chip hardware random number generator which has been seeded by an on-chip entropy source. Intel introduced the feature around 2012, and AMD added support for the instruction in June 2015.

In cryptography, scrypt is a password-based key derivation function created by Colin Percival in March 2009, originally for the Tarsnap online backup service. The algorithm was specifically designed to make it costly to perform large-scale custom hardware attacks by requiring large amounts of memory. In 2016, the scrypt algorithm was published by IETF as RFC 7914. A simplified version of scrypt is used as a proof-of-work scheme by a number of cryptocurrencies, first implemented by an anonymous programmer called ArtForz in Tenebrix and followed by Fairbrix and Litecoin soon after.

Tarsnap is a secure online backup service for UNIX-like operating systems, including BSD, Linux, and OS X. It was created in 2008 by Colin Percival. Tarsnap encrypts data, and then stores it on Amazon S3.

Zstandard is a lossless data compression algorithm developed by Yann Collet at Facebook. Zstd is the corresponding reference implementation in C, released as open-source software on 31 August 2016.

AWS Graviton is a family of 64-bit ARM-based CPUs designed by the Amazon Web Services (AWS) subsidiary Annapurna Labs. The processor family is distinguished by its lower energy use relative to x86-64, static clock rates, and omission of simultaneous multithreading. It was designed to be tightly integrated with AWS servers and datacenters, and is not sold outside Amazon.

References

  1. 1 2 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 14, 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.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.