david wong

Hey! I'm David, cofounder of zkSecurity and the author of the Real-World Cryptography book. I was previously a crypto architect at O(1) Labs (working on the Mina cryptocurrency), before that I was the security lead for Diem (formerly Libra) at Novi (Facebook), and a security consultant for the Cryptography Services of NCC Group. This is my blog about cryptography and security and other related topics that I find interesting.

The missing explanation of ZK-SNARKs: Part 1 posted November 2020

What are ZK-SNARKs and how do they work? This is a question I’ve had for years, and always felt like the resources I found gave no clear intuition as to how all of that stuff worked. So today, after a breakthrough in my own understanding, I thought it would be good to re-share what I’ve learned in a more understandable picture. Something that tells you what is the right way of thinking about these things, and what are the gaps that you can fill for yourself if you want to.

Getting terminology out of the way

The first part of the question is pretty easy to answer. ZK-SNARKs, no matter what their funny name might imply, are simply zero-knowledge proofs that are:

  • non interactive
  • general purpose
  • and succinct

Huh, what are all these words? you ask, intimidated by their vagueness.

Well first, zero-knowledge proofs are cryptographic proofs that you know something, without revealing the something (zero-knowledgeness). That “something” is usually called the witness, but this detail doesn’t matter much. There are a lot of resources about zero-knowledge proofs so I won’t explain much about how they work, or what their exact cryptographic properties are (completeness, soundness, zero-knowledgeness). Zero-knowledge proofs are often seen used to prove that you know the discrete logarithm in some base of an element of some group (e.g. what is $x$ in $g^x \mod p$), or similarly-limited statements.
Limited yes, but still useful!” yells Schnorr, inventor of the Schnorr signature scheme which is fabricated by taking a zero-knowledge proof of the knowledge of a discrete logarithm, and making it non-interactive. A zero-knowledge proof or ZKP is an interactive protocol between a prover (who knows the witness) and a verifier (who has to be convinced). An interactive protocol sucks in the real world, as it often limits the number of potential use-cases of the primitive, and slows down protocols depending on the number of round trips that need to happen between the prover and the verifier. Fortunately, some ZKPs can be constructed without interaction with a verifier. In other words, a prover can simply create a proof, and that proof can be verified by anyone at any point in time later without further help from the prover. When ZKPs are made non-interactive, we simply call them non-interactive zero-knowledge proofs or NIZKs. I talk more about the link between signatures and zero-knowledge proofs here.
ZKPs and NIZKs can also be constructed on much more general statements like “I know an input to some function such that the execution gives some output”, or more specifically “I know $a$ in $f(a, b) = c$”. If this still doesn’t make sense think about the usual example given to illustrate general-purpose ZKPs: “I know the solution of the sudoku”.
We’re almost there: ZK-SNARKs are general-purpose non-interactive zero-knowledge proofs, and more! They are also succinct, meaning that the proofs they produce are small in size and are fast to verify, which makes them so special they deserve to be called ZK-SNARKs. Not every modern proof systems deserve that special classification, for example STARKs don’t :(

As a recap:

  • zero-knowledge proof: a cryptographic proof that you know something, without revealing the something
  • non interactive: a proof that was constructed without the help of a verifier
  • general purpose: a proof of a more general statement, like the knowledge of secret inputs or outputs of a program
  • succinct: a small proof that is fast to verify

But not only did you ask, what are ZK-SNARKs, but you also asked about how they work.

The actual stuff

And oh boy, this is a complex subject to answer. First and foremost, there are many many schemes, too many of them, and so I’m not sure exactly how to answer that question. But I have some idea of how some of them work, and so I imagine that most of them follow that pattern, or improve on it, so let me explain…

There’s two parts to your typical ZK-SNARK:

  1. The proving system, which I'll explain in this post.
  2. The translation or compilation of a program to something the proving system can prove, which I'll explain in part 2 of this post.

The first part is not too hard to understand, while the second sort of requires a graduate course into the subject…

Proving your knowledge of a constrained polynomial

Here it is, remember that one: ZK-SNARKs are all about proving that you know some polynomial $f(x)$ that has some roots. By roots I mean that the verifier has some values in mind (e.g. $1$ and $2$) and the prover must prove that the secret polynomial they have in mind evaluates to $0$ for this values (e.g. $f(1) = f(2) = 0$). By the way, a polynomial that has 1 and 2 as roots (in our example) can be written as $f(x)=(x-1)(x-2)h(x)$ for some polynomial $h(x)$. (If you’re not convinced try to evaluate that at $x=1$ and $x=2$.) So we say that the prover must prove that they know an $f(x)$ and $h(x)$ such that $f(x) = t(x)h(x)$ for some target polynomial $t(x) = (x-1)(x-2)$ (in the example that $1$ and $2$ are the roots that the verifier wants to check).

But that’s it, that’s what ZK-SNARKs proving systems usually provide: something to prove that you know some polynomial. I’m repeating this because the first time I learned about that it made no sense to me: how can you prove that you know some secret input to a program, if all you can prove is that you know a polynomial. Well, that’s why part 2 of this explanation is so difficult: it’s about translating a program into a polynomial. But more on that later.

Back to our proving system, how does one prove that they know such a function $f(x)$? Well they just have to prove that they know an $h(x)$ such that you can write $f(x)$ as $f(x) = t(x)h(x)$. Ugh… Not so fast here. We’re talking about zero-knowledge proofs right? How can we prove this without giving out $f(x)$? Well, by using three tricks!

  1. homomorphic commitments
  2. bilinear pairings
  3. different polynomials evaluate to different values most of the time

So let's go through each of them shall we?

Homomorphic commitments

The first trick is to use commitments to hide the values that we’re sending to the prover. But not only do we hide them, we also want to allow the verifier to perform some operations on them so that they can verify the proof. Specifically verify that if the prover commits on their polynomial $f(x)$ as well as $h(x)$, then we have $$ com(f(x)) = com(t(x)) com(h(x)) = com(t(x)h(x)) $$

where $com(t(x))$ is computed by the verifier as these are the known constraints on the polynomial. These operations are called homomorphic operations and we can’t perform them if we use hash functions as commitment mechanisms. Instead, we can simply “hide the values in the exponent” (e.g. for a value $v$ then send the commitment $g^v \mod{p}$) as these are commitments that allow for these homomorphic operations. (To convince yourself, observe that if $a = bc$ then $g^a = g^b g^c = g^{b+c}$.

Wait, this is not what we wanted… we wanted $g^a = g^{bc}$.

Bilinear pairings

$g^a = (g^b)^c = g^{bc}$ gets us there, but only if $c$ is a known value and not a commitment (e.g. $g^c$). Unfortunately this is a limitation for our proving protocol, as there will be multiplication operations between commitments. This is where bilinear pairings can be used to unblock us, and this is the sole reason why we use bilinear pairings in a ZK-SNARK (really just to be able to multiply the values inside the commitments). I don’t want to go too deep into what bilinear pairings are, but just know that it is just another tool in our toolkit that:

  • Takes two values of our group (the values generates by $g$ raised to different powers modulo $p$) and place them in another group.
  • By moving stuff from one group to the other, we can multiply things that couldn't be multiplied previously.

So using $e$ as the typical way of writing a bilinear pairing, we have $e(g_1, g_2) = h_3$ and we can use it to perform multiplications hidden in the exponent via this one equation:

$$ e(g^b, g^c) = e(g)^{bc} $$

But no more about bilinear pairings! Again that’s the only reason why we use these in ZK-SNARKs. It’s just a trick to make our homomorphic commitments more homomorphic, to allow us to do:

$$ com(f(x)) = com(t(x)) com(h(x)) = com(t(x)h(x)) $$

Where does the succinctness comes from?

Finally, the succinctness of ZK-SNARKs come from the fact that two functions that differ will evaluate to different points most of the time. What this means for us is that if my $f(x)$ is not really equal to $t(x)h(x)$, meaning that I don’t have a polynomial $f(x)$ that really has the roots we’ve chosen with the verifier, then evaluating $f(x)$ and $t(x)h(x)$ at a random point $r$ will not give out the same result (most of the time). In other words for almost all $r$, $f(r) \neq t(r)h(r)$.

This is known as the Schwartz-Zippel lemma, which I pictured in the following illustration.

schwartz zippel lemma

Knowing this, it is enough to prove that $com(f(r)) = com(t(r)h(r))$ for some random point $r$. This is why ZK-SNARKs are so small; by comparing points in a group you end up comparing entire polynomials!

But this is also why there is a “trusted setup” needed before most ZK-SNARKs can work. If a prover learns the random point $r$, then they can forge bad polynomials that will verify. So a trusted setup is about:

  1. creating a random value $r$
  2. committing different exponentiation of it $g^r, g^{r^2}, g^{r^3}, \ldots$ so that they can be used by the prover to compute their polynomial without knowing the point $r$
  3. destroying the value $r$

Does the second point makes sense? If my polynomial as the prover is $f(x) = x^2 + x$ then all I have to do is compute $g^{r^2} g^r$ to obtain a commitment of my polynomial evaluated at that random point $r$.

Part 2 is here.

1 comment

User authentication with passwords, What’s SRP? posted May 2020

The Secure Remote Password (SRP) protocol is first and foremost a Password Authenticated Key Exchange (PAKE). Specifically, SRP is an asymmetric or augmented PAKE: it’s a key exchange where only one side is authenticated thanks to a password. This is usually useful for user authentication protocols. Theoretically any client-server protocol that relies on passwords (like SSH) could be doing it, but instead such protocols often have the password directly sent to the server (hopefully on a secure connection). As such, asymmetric PAKEs offer an interesting way to augment user authentication protocols to avoid the server learning about the user’s password.

Note that the other type of PAKE is called a symmetric or balanced PAKE. In a symmetric PAKE two sides are authenticated thanks to the same password. This is usually useful in user-aided authentication protocols where a user attempts to pair two physical devices together, for example a mobile phone or laptop to a WiFi router. (Note that the recent WiFi protocol WPA3 uses the DragonFly symmetric PAKE for this.)

user (aided) authentication

In this blog post I will answer the following questions:

  • What is SRP?
  • How does SRP work?
  • Should I use SRP today?

What is SRP?

The stanford SRP homepage puts it in these words:

The Secure Remote Password protocol performs secure remote authentication of short human-memorizable passwords and resists both passive and active network attacks. Because SRP offers this unique combination of password security, user convenience, and freedom from restrictive licenses, it is the most widely standardized protocol of its type, and as a result is being used by organizations both large and small, commercial and open-source, to secure nearly every type of human-authenticated network traffic on a variety of computing platforms.

and goes on to say:

The SRP ciphersuites have become established as the solution for secure mutual password authentication in SSL/TLS, solving the common problem of establishing a secure communications session based on a human-memorized password in a way that is crytographically sound, standardized, peer-reviewed, and has multiple interoperating implementations. As with any crypto primitive, it is almost always better to reuse an existing well-tested package than to start from scratch.

But the Stanford SRP homepage seems to date from the late 90s.

SRP was standardized for the first time in 2000 in RFC 2944 - Telnet Authentication: SRP. Nowadays, most people refer to SRP as the implementation used in TLS. This one was specified in 2007 in RFC 5054 - Using the Secure Remote Password (SRP) Protocol for TLS Authentication.

How does SRP work?

The Stanford SRP homage lists 4 different versions of SRP, with the last one being SRP 6. Not sure where version 4 and 5 are, but version 6 is the version that is standardized and implemented in TLS. There is also the revision SRP 6a, but I’m also not sure if it’s in use anywhere today.

SRP registration

To register, Alice sends her identity, a random $salt$, and a salted hash $x$ of her password. Right from the start, you can see that a hash function is used (instead of a password hash function like Argon2) and thus anyone who sees this message can efficiently brute-force the hashed password. Not great. The use of the user-generated salt though, manage to prevent brute-force attacks that would impact all users.

The server can then register Alice by exponentiating a generator of a pre-determined ring (an additive group with a multiplicative operation) with the hashed password. This is an important step as you will see that anyone with the knowledge of $x$ can impersonate Alice.

What follows is the login protocol:

SRP login

You can now see why this is called a password authenticated key exchange, the login flow includes the standard ephemeral key exchange with a twist: the server’s public key $B’$ is blinded or hidden with $v$, a random value derived from Alice’s password. (Note here $k$ is a constant fixed by the protocol so we will just ignore it.)

Alice can only unblinds the server’s ephemeral key by deriving $v$ herself. To do this, she needs the $salt$ she registered with (and this is why the server sends it back to Alice as part of the flow). 
For Alice, the SRP login flow goes like this:

  • Alice re-computes $x = H(salt, password)$ using her password and the salt received from the server.
  • Alice unblinds the server’s ephemeral key by doing $B=B’- kg^x = g^b$
  • Alice then computes the shared secret $S$ by multiplying the results of two key exchanges:
    • $B^a$, the ephemeral key exchange
    • $B^{ux}$, a key exchange between the server’s public key and a value combining the hashed password and the two ephemeral public keys


Interestingly, the second key exchange makes sure that the hashed password and the transcript gets involved in the computation of the shared secret. But strangely, only the public keys and not the full transcript are used.

The server can then compute the shared secret $S$ as well, using the multiplication of the same two key exchanges:

  • $A^b$, the ephemeral key exchange
  • $v^{ub}$, the other key exchange involving the hashed password and the two ephemeral public keys

The final step is for both sides to hash the shared secret and use it as the session key $K = H(S)$. Key confirmation can then happen after both sides make successful use of this session key. (Without key confirmation, you’re not sure if the other side managed to perform the PAKE.)

Should I use SRP today?

The SRP scheme is a much better way to handle user passwords, but it has a number of flaws that make the PAKE protocol less than ideal. For example, someone who intercepts the registration process can then easily impersonate Alice as the password is never directly used in the protocol, but instead the salted hash of the password which is communicated during the registration process.

This was noticed by multiple security researchers along the years. Matthew Green in 2018 wrote Should you use SRP?, in which he says:

Lest you think these positive results are all by design, I would note that there are [five prior versions] of the SRP protocol, each of which contains vulnerabilities. So the current status seems to have arrived through a process of attrition, more than design.

After noting that the combination of multiplication and addition makes it impossible to implement in elliptic curve groups, Matthew Green concludes with:

In summary, SRP is just weird. It was created in 1998 and bears all the marks of a protocol invented in the prehistoric days of crypto. It’s been repeatedly broken in various ways, though the most recent [v6] revision doesn’t seem obviously busted — as long as you implement it carefully and use the right parameters. It has no security proof worth a damn, though some will say this doesn’t matter (I disagree with them.)

Furthermore, SRP is not available in the last version of TLS (TLS 1.3).

Since then, many schemes have been proposed, and even standardized and productionized (for example PAK was standardized by Google in 2010) The IETF 104, March 2019 - Overview of existing PAKEs and PAKE selection criteria has a list:

PAKE list

In the summer of 2019, the Crypto Forum Research Group (CFRG) of the IETF started a PAKE selection process, with goal to pick one algorithm to standardize for each category of PAKEs (symmetric/balanced and asymmetric/augmented):

PAKE CFRG selection process

Two months ago (March 20th, 2020) the CFRG announced the end of the PAKE selection process, selecting:

  • CPace as the symmetric/balanced PAKE (from Björn Haase and Benoît Labrique)
  • OPAQUE as the asymmetric/augmented PAKE (from Stanislaw Jarecki, Hugo Krawczyk, and Jiayu Xu)

Thus, my recommendation is simple, today you should use OPAQUE!

If you want to learn more about OPAQUE, check out chapter 11 of my book real world cryptography.

3 comments

TLS, Pre-Master Secrets and Master Secrets posted March 2016

Everything you want to know about TLS 1.2 is in RFC 5246. But as you may know, if you've read RFCs before, it is not easy to parse (plus they have some sort of double spaces non-sense).

Before we can encrypt/MAC everything with keys to secure our connection, we need to go over a key exchange called the Handshake to safely agree on a set of keys for both parties to use. The handshake can currently use 5 different algorithms to do the key exchange: RSA, Diffie-Hellman, Elliptic Curve Diffie-Hellman and the ephemeral versions of the last two algorithms.

This blogpost is about what happens between this key exchange and the encryption/authentication of data.

The Pre-Master Secret

The pre-master key is the value you directly obtain from the key exchange (e.g. \(g^{ab} \pmod{p}\) if using Diffie-Hellman). Its length varies depending on the algorithm and the parameters used during the key exchange. To make things simpler, we would want a fixed-length value to derive the keys for any cipher suite we would want to use. This is the reason behind a pre master secret. The fixed-length value we'll call master secret. Here the RFC tells us how to compute it from the pre-master secret after having removed the leading zeros bytes.

master_secret = PRF(pre_master_secret, "master secret",
                    ClientHello.random + ServerHello.random)
                    [0..47];

The two random values ClientHello.random and ServerHello.random, sometimes called "nonces", are randomly generated and sent during the ClientHello of each parties. This is to bound the soon-to-be master key to this session. PRF stands for Pseudo-random function, basically some concrete construction that emulates a random oracle: given an input will produce an output computationally indistinguishable from a truly random sequence. But let's move on, and we will see later what exactly is that PRF.

The Master Secret

A master secret is always 48 bytes. So now that we have a fixed length value, we can derive 4 keys from it:

  • client_write_MAC_key
  • server_write_MAC_key
  • client_write_key
  • server_write_key

As you can probably guess, MAC keys are for the authentication and integrity with whatever MAC algorithm you chose in the cipher suite, write keys are for the symmetric encryption.

Interestingly, two keys are generated for every purpose: one key per side. This is mostly by respect of good practices. Always segregate the use of your keys.

The symmetric ciphers chosen in the handshake will dictate how long these keys we generate need to be. Note that AEAD ciphers that combine both authentication and encryption will not need MAC keys but will need two other keys instead: client_write_IV and server_write_IV. This is because their MAC keys are directly derived from the encryption keys.

The same PRF we used on the pre-master key will be used on the master-key over and over until enough bytes have been created for the keys. From the section 6.3 of the RFC:

key_block = PRF(SecurityParameters.master_secret,
                "key expansion",
                SecurityParameters.server_random +
                SecurityParameters.client_random);

The key_block value is then cut into enough keys.

That's it! Here's a recap:

Diffie-Hellman -> pre-master key -> 48bytes master key -> 4 variable-length keys.

The PRF

OK. Now that we got a nice global view of the process, let's dig deeper. The PRF used in TLS 1.2 is discussed here. It is quite different from the PRF used in TLS 1.1, see here.

Remember, for example how it was used to transform the pre-master key into a master key:

master_secret = PRF(pre_master_secret, "master secret",
                    ClientHello.random + ServerHello.random)
                    [0..47];

This is how the PRF function is used:

PRF(secret, label, seed) = P_<hash>(secret, label + seed)

If you want to follow along with code, here's the relevant golang code

P_hash(secret, seed) = HMAC_hash(secret, A(1) + seed) +
                       HMAC_hash(secret, A(2) + seed) +
                       HMAC_hash(secret, A(3) + seed) + ...

where + indicates concatenation, A() is defined as:

A(0) = seed
A(i) = HMAC_hash(secret, A(i-1))

This was a copy/paste from the RFC. To make it clearer: We use the label string ("master secret" in our example) concatenated with the two peers' random values as a seed.

We then MAC the seed with our pre-master secret as the key. We use the first output. Iterating the MAC gives us the subsequent values that we can append to our output.

\[ u_0 = label + serverHello.random + clientHello.random \]

\[ u_i = HMAC(secret, u_{i-1}) \]

\[ output = u_1 , u_2 , \cdots \] This goes on and on until the output is long enough to cover the 48 bytes of the master key (or the 4 keys if we're applying to PRF on the master key).

If P_256 is being used, then SHA-256 is being used. This means the output of HMAC will be 256 bits (32 bytes). To get the 48 bytes of the master key, two iterations are enough, and the remaining bytes can be discarded.

27 comments

What are x509 certificates? RFC? ASN.1? DER? posted April 2015

RFC

So, RFC means Request For Comments and they are a bunch of text files that describe different protocols. If you want to understand how SSL, TLS (the new SSL) and x509 certificates (the certificates used for SSL and TLS) all work, for example you want to code your own OpenSSL, then you will have to read the corresponding RFC for TLS: rfc5280 for x509 certificates and rfc5246 for the last version of TLS (1.2).

rfc ex

x509

x509 is the name for certificates which are defined for:

informal internet electronic mail, IPsec, and WWW applications

There used to be a version 1, and then a version 2. But now we use the version 3. Reading the corresponding RFC you will be able to read such structures:

Certificate  ::=  SEQUENCE  {
    tbsCertificate       TBSCertificate,
    signatureAlgorithm   AlgorithmIdentifier,
    signatureValue       BIT STRING  }

those are ASN.1 structures. This is actually what a certificate should look like, it's a SEQUENCE of objects.

  • The first object contains everything of interest that will be signed, that's why we call it a To Be Signed Certificate
  • The second object contains the type of signature the CA used to sign this certificate (ex: sha256)
  • The last object is not an object, its just some bits that correspond to the signature of the TBSCertificate after it has been encoded with DER

ASN.1

It looks small, but each object has some depth to it.

The TBSCertificate is the biggest one, containing a bunch of information about the client, the CA, the publickey of the client, etc...

TBSCertificate  ::=  SEQUENCE  {
    version         [0]  EXPLICIT Version DEFAULT v1,
    serialNumber         CertificateSerialNumber,
    signature            AlgorithmIdentifier,
    issuer               Name,
    validity             Validity,
    subject              Name,
    subjectPublicKeyInfo SubjectPublicKeyInfo,
    issuerUniqueID  [1]  IMPLICIT UniqueIdentifier OPTIONAL,
                         -- If present, version MUST be v2 or v3
                          subjectUniqueID [2]  IMPLICIT UniqueIdentifier OPTIONAL,
                      -- If present, version MUST be v2 or v3
     extensions      [3]  EXPLICIT Extensions OPTIONAL
                      -- If present, version MUST be v3
}

DER

A certificate is of course not sent like this. We use DER to encode this in a binary format.

Every fieldname is ignored, meaning that if we don't know how the certificate was formed, it will be impossible for us to understand what each value means.

Every value is encoded as a TLV triplet: [TAG, LENGTH, VALUE]

For example you can check the GITHUB certificate here

github cert

On the right is the hexdump of the DER encoded certificate, on the left is its translation in ASN.1 format.

As you can see, without the RFC near by we don't really know what each value corresponds to. For completeness here's the same certificate parsed by openssl x509 command tool:

x509 openssl parsed

How to read the DER encoded certificate

So go back and check the hexdump of the GITHUB certificate, here is the beginning:

30 82 05 E0 30 82 04 C8 A0 03 02 01 02

As we saw in the RFC for x509 certificates, we start with a SEQUENCE.

Certificate  ::=  SEQUENCE  {

Microsoft made a documentation that explains pretty well how each ASN.1 TAG is encoded in DER, here's the page on SEQUENCE

30 82 05 E0

So 30 means SEQUENCE. Since we have a huge sequence (more than 127 bytes) we can't code the length on the one byte that follows:

If it is more than 127 bytes, bit 7 of the Length field is set to 1 and bits 6 through 0 specify the number of additional bytes used to identify the content length.

(in their documentation the least significant bit on the far right is bit zero)

So the following byte 82, converted in binary: 1000 0010, tells us that the length of the SEQUENCE will be written in the following 2 bytes 05 E0 (1504 bytes)

We can keep reading:

30 82 04 C8 A0 03 02 01 02

Another Sequence embedded in the first one, the TBSCertificate SEQUENCE

TBSCertificate  ::=  SEQUENCE  {
    version         [0]  EXPLICIT Version DEFAULT v1,

The first value should be the version of the certificate:

A0 03

Now this is a different kind of TAG, there are 4 classes of TAGs in ASN.1: UNIVERSAL, APPICATION, PRIVATE, and context-specific. Most of what we use are UNIVERSAL tags, they can be understood by any application that knows ASN.1. The A0 is the [0] (and the following 03 is the length). [0] is a context specific TAG and is used as an index when you have a series of object. The github certificate is a good example of this, because you can see that the next index used is [3] the extensions object:

TBSCertificate  ::=  SEQUENCE  {
    version         [0]  EXPLICIT Version DEFAULT v1,
    serialNumber         CertificateSerialNumber,
    signature            AlgorithmIdentifier,
    issuer               Name,
    validity             Validity,
    subject              Name,
    subjectPublicKeyInfo SubjectPublicKeyInfo,
    issuerUniqueID  [1]  IMPLICIT UniqueIdentifier OPTIONAL,
                         -- If present, version MUST be v2 or v3
                          subjectUniqueID [2]  IMPLICIT UniqueIdentifier OPTIONAL,
                      -- If present, version MUST be v2 or v3
     extensions      [3]  EXPLICIT Extensions OPTIONAL
                      -- If present, version MUST be v3
}

Since those obects are all optionals, skipping some without properly indexing them would have caused trouble parsing the certificate.

Following next is:

02 01 02

Here's how it reads:

  _______ tag:      integer
 |   ____ length: 1 byte
 |  |   _ value:  2
 |  |  |
 |  |  |
 v  v  v
02 01 02 

The rest is pretty straight forward except for IOD: Object Identifier.

Object Identifiers

They are basically strings of integers that reads from left to right like a tree.

So in our Github's cert example, we can see the first IOD is 1.2.840.113549.1.1.11 and it is supposed to represent the signature algorithm.

So go to http://www.alvestrand.no/objectid/top.html and click on 1, and then 1.2, and then 1.2.840, etc... until you get down to the latest branch of our tree and you will end up on sha256WithRSAEncryption.

Here's a more detailed explanation on IOD and here's the microsoft doc on how to encode IOD in DER.

20 comments

Why I’m Writing A Book On Cryptography posted July 2020

I’ve now been writing a book on applied cryptography for a year and a half. I’m nearing the end of my journey, as I have one last ambitious chapter left to write: next-generation cryptography (a chapter that I’ll use to talk about cryptography that will become more and more practical: post-quantum cryptography, homomorphic encryption, multi-party computation, and zk-SNARKs).

I’ve been asked multiple times why write a new book about cryptography? and why should I read your book?. To answer this, you have to understand when it all started…

A picture is worth a thousand words

Today if you want to learn about almost anything, you just google it. Yet, for cryptography, and depending on what you're looking for, resources can be quite lacking.

It all started a long time ago. For a class, I had to implement a differential power analysis attack, a breakthrough in cryptanalysis as it was the first side-channel attack to be published. A differential power analysis uses the power consumption of a device during an encryption to leak its private key. At the time, I realized that great papers could convey great ideas with very little emphasis on understanding. I remember banging my head against the wall trying to figure out what the author of the white paper was trying to say. Worse, I couldn’t find a good resource that explained the paper. So I banged my head a bit more, and finally I got it. And then I thought I would help others. So I drew some diagrams, animated them, and recorded myself going over them. That was my first screencast.

This first step in education was enough to make me want to do more. I started making more of these videos, and started writing more articles about cryptography on this blog (today totaling more than 500 articles).

we want to know

I realized early that diagrams were extremely helpful to understand complicated concepts, and that strangely most resources in the field shied away from them.

For example, anyone in cryptography who thinks about AES-CBC would immediately think about the following wikipedia diagram:

aes cbc

So here I was, trying to explain everything I learned, and thinking hard about what sorts of simple diagrams could easily convey these complex ideas. That’s when I started thinking about a book, years and years before Manning Publications would reach out to me with a book deal.

The applied cryptographer curriculum


I hadn’t started cryptography due to a long-life passion. I had finished a bachelor in theoretical mathematics and didn’t know what was next for me. I had also been programming my whole life, and I wanted to reconcile the two. Naturally, I got curious about cryptography, which seemed to have the best of both world, and started reading the different books at my disposal. I quickly discovered my life's calling.

Some things were annoying me though. In particular, the long introductions that would start with history. I was only interested in the technicalities, and always had been. I swore to myself, if I ever wrote a book about cryptography, I would not write a single line on Vigenère ciphers, Caesar ciphers, and others.

And so after applying to the masters of Cryptography at the university of Bordeaux, and obtaining a degree in the subject, I thought I was ready for the world. Little did I know. What I thought was a very applied degree actually lacked a lot on the real world protocols I was about to attack. I had spent a lot of time learning about the mathematics of elliptic curves, but nothing about how they were used in cryptographic algorithms. I had learned about LFSRs, and ElGamal, and DES, and a series of other cryptographic primitives that I would never see again.

When I started working in the industry at Matasano, which then became NCC Group, my first gig was to audit OpenSSL (the most popular TLS implementation). Oh boy, did it hurt my brain. I remember coming back home every day with a strong headache. What a clusterfuck of a library. I had no idea at the time that I would years later become a co-author of TLS 1.3.

sign

But at that point I was already thinking: this is what I should have learned in school. The knowledge I’m getting now is what would have been useful to prepare me for the real world. After all, I was now a security practitioner specialized in cryptography. I was reviewing real-world cryptographic applications. I was doing the job that one would wish they had after finishing a cryptography degree. I implemented, verified, used, and advised on what cryptographic algorithms to use.

This is the reason I’m the first reader of the book I’m writing. This is what I would have written to my past self in order to prepare me for the real world.

The use of cryptography is where most of the bugs are

My consulting job led me to audit many real world cryptographic applications like the OpenSSL, the encrypted backup system of Google, the TLS 1.3 implementation of Cloudflare, the certificate authority protocol of Let’s Encrypt, the sapling protocol of Zcash, the threshold proxy re-encryption scheme of NuCypher and dozens and dozens of other real-world cryptographic applications that I unfortunately cannot mention publicly.

Early in my job, I was tasked to audit the custom protocol a big corporation (that I can’t name) had written to encrypt their communications. It turns out that, they were signing everything but the ephemeral keys, which completely broke the whole protocol (as one could have easily replaced the ephemeral keys). A rookie mistake from anyone with some experience with secure transport protocols, but something that was missed by people who thought they were experienced enough to roll their own crypto. I remember explaining the vulnerability at the end of the engagement, and a room full of engineers turning silent for a good 30 seconds.

This story repeated itself many times during my career. There was this time where while auditing a cryptocurrency for another client, I found a way to forge transactions from already existing ones (due to some ambiguity of what was being signed). Looking at TLS implementations for another client, I found some subtle ways to break an RSA implementation, which in turned transformed into a white paper (with one of the inventor of RSA) leading to a number of Common Vulnerabilities and Exposures (CVEs) reported to a dozen of open source projects. More recently, reading about Matrix as part of writing my book, I realized that their authentication protocol was broken, leading to a break of their end-to-end encryption.

comic

There’s so many details that can unfortunately collapse under you, when making use of cryptography. At that point, I knew I had to write something about it. This is why my book contains many of these anecdotes.

As part of the job, I would review cryptography libraries and applications in a multitude of programming languages. I discovered bugs (for example CVE-2016-3959 in Golang’s standard library), I researched ways that libraries could fool you into misusing them (for example see my paper How to Backdoor Diffie-Hellman), and I advised on what libraries to use. Developers never knew what library to use, and I always found the answer to be tricky.

I went on to invent the disco protocol, and wrote a fully-featured cryptographic library in less than 1,000 lines of code in several languages. Disco only relied on two cryptographic primitives: the permutation of SHA-3 and curve25519. Yes, from only these two things in 1,000 lines of code a developer could do any type of authenticated key exchange, signatures, encryption, MACs, hashing, key derivation, etc. This gave me a unique perspective as to what a good cryptographic library was supposed to be.

I wanted my book to contain these kind of practical insights. So naturally, the different chapters contain examples on how to do crypto in different programming languages, using well-respected cryptographic libraries.

A need for a new book?

As I was giving one of my annual cryptography training at Black Hat, one student came to me and asked if I could recommend a good book or online course on cryptography. I remember advising the student to read the book from Boneh & Shoup and Cryptography I from Boneh on Coursera.

The student told me “Ah, I tried, it’s too theoretical!”. This answer stayed with me. I disagreed at first, but slowly realized that they were right. Most of these resources were pretty heavy in math, and most developers interacting with cryptography don’t want to deal with math. 
What else was there for them? The other two somewhat respected resources at the time were Applied Cryptography and Cryptography Engineering (both from Schneier). But these books were starting to be quite outdated. Applied Cryptography spent 4 chapters on block ciphers, with a whole chapter on cipher modes of operation but none on authenticated encryption. Cryptography Engineering had a single mention of elliptic curve cryptography (in a footnote).

On the other hand, many of my videos or blog posts were becoming good primary references for some cryptographic concepts.

I knew I could do something special.

Gradually, many of my students started becoming interested in cryptocurrencies, asking more and more questions on the subject. At the same time, I started to audit more and more cryptocurrency applications. I finally moved to a job at Facebook to work on Libra. Cryptocurrency was now one of the hottest field to work on, mixing a multitude of extremely interesting cryptographic primitives that so far had seen no real-world use case (zero knowledge proofs, aggregated signatures, threshold cryptography, multi-party computations, consensus protocols, cryptographic accumulators, verifiable random functions, verifiable delay functions, ... the list goes on)

libra

I was now in a unique position.

I knew I could write something that would tell students, developers, consultants, security engineers, and others, what modern applied cryptography was all about.

book

This was going to be a book with very little formulas, but filled with many diagrams.

This was going to be a book with little history, but filled with modern stories about cryptographic failures that I had witnessed for real.

This was going to be a book with little about legacy algorithms, but filled with cryptography that I've personally seen being used at scale: TLS, the Noise protocol framework, Wireguard, the Signal protocol, cryptocurrencies, HSMs, threshold cryptography, and so on.

This was going to be a book with little theoretical cryptography, but filled with what could become relevant: password-authentication key exchanges, zero-knowledge proofs, post-quantum cryptography, and so on.

Real-World Cryptography

When Manning Publications reached out to me in 2018, asking if I wanted to write a book on cryptography for them, I already knew the answer. I already knew what I wanted to write about. I had just been waiting for someone to give me the opportunity, the excuse to spend my time writting the book I had in mind.

Coincidentally, they had a series of "real-world" book, and so naturally I suggested that my book extend it.

book

Real-World Cryptography is available for free in early-access.

I want this to be the best book on applied cryptography. For this reason, if you have any feedback to give, please send it my way :)

The book should be ready in print for the end of the year.

22 comments

Let's Encrypt Overview posted June 2015

letsencrypt

What is Let's Encrypt?

Basically, it's a way to get a quick x509 certificate for your server without knowing much about what is a x509 certificate:

You have a website. You want people to be able to log in on it from starbucks without the guy sitting at a near table reading the passwords in clear from the packets you're sending everyone around you. So you google a few random keywords like "secure website https" and you end up with a bunch of links and services (which may not be free) and you suddenly have to understand what are certificates, PKI, x509, public-key cryptography, RSA, FQDN, haaa.... Well, worry no more, Let's Encrypt was thought so that you wouldn't have to go through all that trouble and destroy your server on the way.

Oh and yeah. It's for free. But is hasn't been released yet.

How does it work?

You can learn more reading their technical overview, or some of their videos... or read my tl;dr:

  1. You download their program on your server that has the address www.example.com:
sudo apt-get install lets-encrypt
  1. You run it as sudo telling it you want to get a certificate for your domain
lets-encrypt example.com

And voila.

Behing the curtains this is what happens:

ACME

  1. lets-encrypt will generate a pair of RSA private key/public key and contact the CA with your public key.

  2. The CA will register your public key

  3. The program will then ask the CA to verify your domain.

  4. The CA will answer with a set of challenges. These are some tasks you can complete to prove to the CA you own that domain. One of the common one is to upload a certain file at a certain address of that domain.

  5. The program you installed will then do that for you and poll the CA for a confirmation

  6. The CA will tell you "OK man, all is good".

  7. The program will then generate another long term pair of private key/public key, generate a CSR (Certificate Signing Request) with the new public key and send that CSR to the CA.

  8. The CA will extract the information, create a beautiful x509 certificate, sign it and send it back to you.

  9. lets-encrypt will install the certificate on your server and set certain options (or not) to force https

By the way, the certificate you will get will be a DV certificate, meaning that they only verified that you owned the domain, nothing more. If you want an EV certificate this is what you will have to go through (according to wikipedia):

  • Establish the legal identity as well as the operational and physical presence of website owner;
  • Establish that the applicant is the domain name owner or has exclusive control over the domain name; and
  • Confirm the identity and authority of the individuals acting for the website owner, and that documents pertaining to legal obligations are signed by an authorised officer.

But how does it really work?

So! The lets-encrypt program you run on your server is open sourced here: https://github.com/letsencrypt/lets-encrypt-preview. It is called lets-encrypt-preview I guess because it isn't done yet. It's written in Python and has to be run in sudo so that it can do most of the work for you. Note that it will install the certificates on your server only if you are using Apache or Nginx. Also, the address of the CA is hardcoded in the program so be sure to use the official lets-encrypt.

The program installed on the CA is also open sourced! So that anyone can publicly review and audit the code. It's called Boulder and it's here: https://github.com/letsencrypt/boulder and written in Go.

Lets-encrypt and Boulder both use the protocol ACME for Automated Certificate Management Environment specified here as a draft: https://letsencrypt.github.io/acme-spec/

ACME

ACME spec

ACME is written like a RFC. It actually wants to become an RFC eventually! So if you've read RFCs before you should feel like home.

The whole protocol is happening over TLS. As a result the exchanges are encrypted, you know that you are talking to the CA you want to talk to (eventhough you might not use DNSSEC) and replay attacks should be avoided.

The whole thing is actually a RESTful API. The client, you, can do GET or POST queries to certains URI on the CA webserver.

Registration

The first thing you want to do is register. Registration is actually done by generating a new pair of RSA keys and sending them the public key (along with your info).

ACME specifies that you should use JWS for the transport of data. Json Web Signature. It's basically Json with authentication (so that you can sign your messages). It actually uses a variant of JWS called Jose that doesn't use a normal base64 encoding but that's all you should know for now. If you really want to know more there is an RFC for it.

So here what a request should look like with JWS (your information are sent unencrypted in the payload field (but don't worry, everything is encrypted anyway because the exchange happens over TLS)):

POST /acme/new-registration HTTP/1.1
Host: example.com

{
 "payload":"<payload contents>",
 "signatures":[
  {"protected":"<integrity-protected header 1 contents>",
   "header":<non-integrity-protected header 1 contents>,
   "signature":"<signature 1 contents>"}
}

Boulder will check the signature with the public key you passed, verify the information you gave and eventually add you to its database.

Once you are registered, you can perform several actions:

  • Update your infos
  • Get one domain authorized (well actually as many as you'd like)

The server will authenticate you because you will now send your public key along AND you will sign your requests. This all runs on top of TLS by the way. I know I already said that.

Boulder's guts

boulder

Boulder is separated in multiple components, this makes the code clearer and ensure that every piece of code does what it is supposed to do and nothing more.

One of the components is called the Web-Front-End (WFE) and is the only one accepting queries from the Client. It parses them, verifies them and passes them to the Registration Authority (RA) that combines the other authorities together to produce a response. The response is then passed back to the WFE and to the client over the ACME protocol. Are you following?

TWe'll see what other authorities the RA has access to in the next queries the client can do. But just to talk about the previous query, the new registration query, the RA talks to the Storage Authority that deals with the database (Which is currently SQLlite) to register your new account.

All the components can be run from a single machine (for the exception of the CA that runs on another library), but they can also be run seperately from different machines that will communicate on the same network via AMQP.

New Authorization

Now that you are registered, you have to validate a domain before you can request a certificate.

You make a request to a certain URI.

Well to be exact you make a POST request to /new-authz, and the response will be 201 if it works. It will also give you some information about where you can go next to do stuff (/authz)

Here's the current list of API calls you can do and the relevant answers.

API calls

The server will pass the info to the Policy Authority (PA) and ask it if it is willing to accept such a domain. If so, it will then answer with a list of challenges you can complete to prove you own the domain, along with combinations of accepted challenges to complete. For now they only have two challenges and you can complete either one:

  • SimpleHTTPS

  • DVSNI

If you choose SimpleHTTPS the lets-encrypt client will generate a random value and upload something at the address formed by a random value the CA sent you and the random value you generated.

If you choose DVSNI, the client will create a TLS certificate containing some of the info of the challenge and with the public key associated to his account.

The client then needs to query the CA again and the CA's Validation Authority (VA) will either check that the file has been uploaded or will perform a handshake with the client's server and verify that specific fields of the certificates have been correctly filled. If everything works out the VA will tell the RA that will tell the WFE that will tell you...

After that you are all good, you can now make a Certificate Signing Request :)

New Certificate

The agent will now generate a new pair of private key/public key. And create a CSR with it. So that your long term key used in your certificate is not the same as your let's encrypt account.

CSR

a CSR example, containing the identifier and the public key

After reception of it, the Web-Front-End of Boulder will pass it to the Registration Authority (RA) which will pass it to the Certificate Authority (CA) that will do all the work and will eventually sign it and send it back to the chain.

1: Client ---new-cert--> WFE
2:                       WFE ---NewCertificate--> RA
3:                                                RA ---IssueCertificate--> CA
4:                                                                          CA --> CFSSL
5:                                                                          CA <-- CFSSL
6:                                                RA <------return--------- CA
7:                       WFE <------return------- RA
8: Client <------------- WFE

Oh and also. the CA is talking to a CFSSL server which is CloudFlare's PKI Toolkit, a nice go library that you can use for many things and that is used here to act as the CA. CFSSL has recently pushed code to be compatible with the use of HSM which is a hardware device that you HAVE to use to sign keys when you are a CA.

After reception the lets-encrypt client will install the fresh certificate along with the chain to the root on your server and voila!

You can now revoke a certificate in the same way, but interestingly you won't need to sign the request with your account key, but with the private key associated to your certificate's public key. So that even if you lose your agent's key you can still revoke the certificate.

Other stuff

There are a bunch of stuff that you will be able to do with the lets-encrypt client but that haven't been implemented yet:

  • Renew a certificate
  • Read the Terms of Service
  • Query OCSP requests (see if a certificate has been revoked) ...

Moar

This post is a simplification of the protocol. If you want to know more and don't want to dig in the ACME specs right now you can also take a look at Boulder's flow diagrams.

key ceremony

If you've followed the news you should have seen that Let's Encrypt just generated its root certificate along with several other certificates: https://letsencrypt.org/2015/06/04/isrg-ca-certs.html

This is because when you are a CA you are suppose to keep the root certificate offline. So you sign a (few) certificate(s) with that root, you lock that root and you use the signed certificate(s) to sign other certificates. This is all very serious because if something goes wrong with the root certificate, you can't revoke anything and well... the internet goes wrong as a result (until vendors start removing these from their list of trusted roots).
So the keys for the certificate have to be generated during a "ceremony" where everything is filmed and everyone must authenticate oneself at least with two different documents, etc... Check Wikipedia's page on Key Ceremony it's "interesting".

Also, I received a note from Seth David Schoen and I thought that was an interesting anecdote to share :)

the name "Boulder" is a joke from the American children's cartoon Looney Tunes:
https://en.wikipedia.org/wiki/Wile_E._Coyote_and_The_Road_Runner
This is because the protocol that Boulder implements is called ACME, which was also the name of the company that made the products unsuccessfully used by the coyote to attempt to catch the roadrunner. https://en.wikipedia.org/wiki/Acme_Corporation
Two of those products were anvils (the original name of the CA software) and boulders.

22 comments

How does PLONK work? Part 8: A polynomial dance posted August 2021

In this eighth video, I explain how the prover and the verifier can perform a "polynomial dance" in order to construct the circuit polynomial $f$. The principle is simple: the prover doesn't want to leak information about the private inputs and the intermediary values in the circuit, and the verifier doesn't want to give the prover too much freedom in the way they construct the circuit polynomial $f$.

Part 9 is here. Check the full series here.

comment on this story