Cryptography

Proving that a choice was made in good faith

Posted on by John

How can you prove that a choice was made in good faith? For example, if your company selects a cohort of people for random drug testing, how can you convince those who were chosen that they weren’t chosen deliberately? Would a judge find your explanation persuasive? This is something I’ve helped companies with.

It may be impossible to prove that a choice was not deliberate, but you can show good faith by providing evidence that the choice was deliberate by a different criteria than the one in question.

I’ll give four examples, three positive and one negative.

Cliff RNG

My previous three blog posts looked at different aspects of the Cliff random number generator. The generator needs a seed between 0 and 1 to start. Suppose I chose 0.8121086949937715 as my seed. On the one hand, that’s a number with no apparent special features. But you might ask “Hey, why that number?” and you’d be right. I show in the first post in the series how that number was chosen to make the generator start off producing duplicate output.

In the next two posts in the series, I chose π – 3 as my seed. That’s a recognizable number and obviously a deliberate choice. But it has no apparent connection to the random number generator, and so it’s reasonable to assume that the seed wasn’t chosen to make the generator look good or bad.

SHA-2

The SHA-2 cryptographic hash function seventy two 32-bit numbers for initial state that needed to be “random” in some sense. But if the values were actually chosen at random, critics would suspect that the values were chosen to provide a back door. And maybe there is a clever way to pick the initial state that provides a non-obvious exploitable weakness.

The designers of SHA-2 chose the square roots of the first consecutive primes to fill one set of constants, and the cube roots of the first consecutive primes to fill another. See code here.

The initial state is definitely not random. Someone looking at the state would eventually discover where it came from. So while the choice was obviously deliberate, but apparently not designed by any cryptographic criteria.

Curve 25519

Daniel Bernstein’s elliptic curve Curve25519 is widely trusted in part because Bernstein made his design choices transparent. The curve is

y² = x³ + 486662x² + x

over the finite field with 2255-19 elements, hence the name.

2255-19 is the largest prime less than 2255, and being close to 2255 makes the method efficient to implement. The coefficient 48666 is less obvious. But Bernstein explains in his paper that he took the three smallest possible values of this parameter that met the explicit design criteria, and then rejected two of them on objective grounds described at the bottom of the paper.

NIST P-384

The design of elliptic curve NIST P-384 is not as transparent as that of Curve25519 which has lead to speculation that NIST may have designed the curve to have a back door.

The curve has has Weierstrass form

y² = x³ – 3x + b

over the finite field with p elements where

p = 2384 – 2128 – 296 + 232 – 1.

As with Curve25519, the choice of field size was motivated by efficiency; the pattern of powers of 2 enables some tricks for efficient implementation. Also, there are objective reasons why the linear coefficient is -3. But the last coefficient b is the 383-bit number

27580193559959705877849011840389048093056905856361568521428707301988689241309860865136260764883745107765439761230575

which has raised some eyebrows. NIST says the value was chosen at random, though not directly. More specifically, NIST says it first generated a certain 160-bit random number, then applied a common key stretching algorithm to obtain b above. Researchers are divided over whether they believe this. See more in this post.

Conclusion

Sometimes you can’t prove that a choice wasn’t deliberate. In that case the best you can do is show that the choice was deliberate, but by an innocent criteria, one unrelated to the matter at hand.

I tried to do this in the Cliff RNG blog posts by using π as my seed. I couldn’t actually use π because the seed had to be between 0 and 1, but there’s an obvious way to take π and produce a number between 0 and 1.

The designers of SHA-2 took a similar route. Just as π is a natural choice for a real number, primes are natural choices for integers. They couldn’t use integers directly, but they made complicated patterns from simple integers in a natural way by taking roots.

Daniel Bernstein gained the cryptography community’s trust by making his design criteria transparent. Given his criteria, the design was almost inevitable.

NIST was not as persuasive as Daniel Bernstein. They claim to have chosen a 160-bit number at random, and they may very well have. But there’s no way to know whether they generated a lot of 160-bit seeds until they found one that resulted in a constant term that has some special property. They may have chosen their seed in good faith, but they have a not been completely persuasive.

Sometimes it’s not enough to act in good faith; you have to make a persuasive case that you acted in good faith.

Encryption as secure as factoring

Posted on by John

RSA encryption is based on the assumption that factoring large integers is hard. However, it’s possible that breaking RSA is easier than factoring. That is, the ability to factor large integers is sufficient for breaking RSA, but it might not be necessary.

Two years after the publication of RSA, Michael Rabin created an alternative that is provably as hard to break as factoring integers.

Like RSA, Rabin’s method begins by selecting two large primes, p and q, and keeping them secret. Their product n = pq is the public key. Given a message m in the form of a number between 0 and n, the cipher text is simply

c = m² mod n.

Rabin showed that if you can recover m from c, then you can factor n.

However, Rabin’s method does not decrypt uniquely. For every cipher text c, there are four possible clear texts. This may seem like a show stopper, but there are ways to get around it. You could pad messages with some sort of hash before encryption so that is extremely unlikely that more than one of the four decryption possibilities will have the right format. It is also possible to make the method uniquely invertible by placing some restrictions on the primes used.

I don’t know that Rabin’s method has been used in practice. I suspect that the assurance that attacks are as hard as factoring integers isn’t valuable enough to inspire people to put in the effort to harden the method for practical use [1].

There’s growing suspicion that factoring may not be as hard as we’ve thought. And we know that if large scale quantum computing becomes practical, factoring integers will be easy.

My impression is that researchers are more concerned about a breakthrough in factoring than they are about a way to break RSA without factoring [2, 3].

Related posts

[1] One necessary step in practical implementation of Rabin’s method would be to make sure m > √n. Otherwise you could recover m by taking the integer square root rather than having to take a modular square root. The former is easy and the latter is hard.

[2] There are attacks against RSA that do not involve factoring, but they mostly exploit implementation flaws. They are not a frontal assault on the math problem posed by RSA.

[3] By “breaktrhough” I meant a huge improvement in efficiency. But another kind of breaktrough is conceivable. Someone could prove that factoring really is hard (on classical computers) by establishing a lower bound. That seems very unlikely, but it would be interesting. Maybe it would spark renewed interest in Rabin’s method.

Beating the odds on the Diffie-Hellman decision problem

Posted on by John

There are a couple variations on the Diffie-Hellman problem in cryptography: the computation problem (CDH) and the decision problem (DDH). This post will explain both and give an example of where the former is hard and the latter easy.

The Diffie-Hellman problems

The Diffie-Hellman problems are formulated for an Abelian group. The main group we have in mind is the multiplicative group of non-zero integers modulo a large prime p. But we start out more generally because the Diffie-Hellman problems are harder over some groups than others as we will see below.

Let g be the generator of a group. When we think of the group operation written as multiplication, this means that every element of the group is a power of g.

Computational Diffie-Hellman problem

Let a and b be two integers. Given ga and gb, the CDH problem is to compute gab. Note that the exponent is ab and not a+b. The latter would be easy: just multiply ga and gb.

To compute gab we apparently need to know either a or b, which we are not given. Solving for either exponent is the discrete logarithm problem, which is impractical for some groups.

It’s conceivable that there is a way to solve CDH without solving the discrete logarithm problem, but at this time the most efficient attacks on CDH compute discrete logs.

Diffie-Hellman key exchange

Diffie-Hellman key exchange depends on the assumption that CDH is a hard problem.

Suppose Alice and Bob both agree on a generator g, and select private keys a and b respectively. Alice sends Bob ga and Bob sends Alice gb. This doesn’t reveal their private keys because the discrete logarithm problem is (believed to be) hard. Now both compute gab and use it as their shared key. Alice computes gab by raising gb to the power a, and Bob computes gab by raising ga to the power b.

If someone intercepted the exchange between Alice and Bob, they would possess ga and gb and would want to compute gab. This the the CDH.

When working over the integers modulo a large prime p, CDH is hard if p-1 has a large factor, such as when p – 1 = 2q for a prime q. If p-1 has only small factors, i.e. if p-1 is “smooth”, then the discrete logarithm problem is tractable via the Silver-Pohlig-Hellman algorithm [1]. But if p is large and p-1 has a large prime factor, CDH is hard as far as we currently know.

Decision Diffie-Hellman problem

The DDH problem also starts with knowledge of ga and gb. But instead of asking to compute gab it asks whether one can distinguish gab from gc for a randomly chosen c with probability better than 0.5.

Clearly DDH is weaker than CDH because if we can solve CDH we know the answer to the DDH question with certainty. Still, the DDH problem is believed to be hard over some groups, such as certain elliptic curves, but not over other groups, as illustrated below.

DDH for multiplicative group mod p

Suppose we’re working in the multiplicative group of non-zero integers modulo a prime p. Using Legendre symbols, which are practical to compute even for very large numbers, you can determine which whether ga is a square mod p, which happens if and only if a is even. So by computing the Legendre symbol for ga mod p, we know the parity of a. Similarly we can find the parity of b, and so we know the parity of ab. If ab is odd but gc is a square mod p, we know that the answer to the DDH problem is no. Similarly if ab is even but gc is not a square mod p, we also know that the answer to the DDH problem is no.

Since half the positive integers mod p are squares, we can answer the DDH problem with certainty half the time by the parity argument above. If our parity argument is inconclusive we have to guess. So overall we can answer he DDH problem correctly with probability 0.75.

Related posts

[1] As is common when you have a lot of names attached to a theorem, there were multiple discoveries. Silver discovered the algorithm first, but Pohlig and Hellman discovered it independently and published first.

Twisted elliptic curves

Posted on by John

This morning I was sitting at a little bakery thinking about what to do before I check out of my hotel. I saw that the name of the bakery was Twist Bakery & Cafe, and that made me think of writing about twisted elliptic curves when I got back to my room.

Twist of an elliptic curve

Suppose p is an odd prime and let E be the elliptic curve with equation

y² = x³ + ax² + bx + c

where all the variables come from the integers mod p. Now pick some d that is not a square mod p, i.e. there is no x such that x² – d is divisible by p. Then the curve E‘ with equation

dy² = x³ + ax² + bx + c

is a twist of E. More explicit it’s a quadratic twist of E. This is usually what people have in mind when they just say twist with no modifier, but there are other kinds of twists.

Let’s get concrete. We’ll work with integers mod 7. Then the squares are 1, 4, and 2. (If that last one looks strange, note that 3*3 = 2 mod 7.) And so the non-squares are 3, 5, and 6. Suppose our curve E is

y² = x³ + 3x + 2.

Then we can form a twist of E by multiplying the left side by 3, 5, or 6. Let’s use 3. So E‘ given by

3y² = x³ + 3x + 2

is a twist of E.

Twisted curve

There’s something potentially misleading in the term “twisted curve”. The curve E‘ is a twist of E, so E‘ is twisted relative to E, and vice versa. You can’t say E‘ is twisted and E is not.

But you might object that E‘ has the form

dy² = x³ + ax² + bx + c

where d is a non-square, and E does not, so E‘ is the one that’s twisted. But a change of variables can leave the curve the same while changing the form of the equation. Every curve has an equation in which the coefficient of y² is 1 and a form in which the coefficient is a non-square. Specifically,

dy² = x³ + ax² + bx + c

and

y² = x³ + dax² + d²bx + d³c

specify the same curve.

The two curves E and E‘ are not isomorphic over the field of integers mod p, but they are isomorphic over the quadratic extension of the integers mod p. That is, if you extend the field by adding the square root of d, the two curves are isomorphic over that field.

Partitioning x coordinates

For a given x, f(x) = x³ + ax² + bx + c is either a square or a non-square. If it is a square, then

y² = f(x)

has a solution and

dy² = f(x)

does not. Conversely, if f(x) is not a square, then

dy² = f(x)

has a solution and

y² = f(x)

does not. So a given x coordinate either corresponds to a point on E or a point on E‘, but not both.

Application to cryptography

In elliptic curve cryptography, it’s good if not only is the curve you’re using secure, so are its twists. Suppose you intend to work over a curve E, and someone sends you an x coordinate that’s not on E. If you don’t check whether x corresponds to a point on E, you are effectively working on a twist E‘ rather than E. That can be a security hole if E‘ is not as secure a curve as E, i.e. if the discrete logarithm problem on E‘ can be solved more efficiently than the same problem on E.

Related posts

Homomorphic encryption

Posted on by John

A function that satisfies

f(x*y) = f(x)*f(y)

is called a homomorphism. The symbol “*” can stand for any operation, and it need not stand for the same thing on both sides of the equation. Technically * is the group operation, and if the function f maps elements of one group to another, the group operation may be different in the two groups.

Examples

Below are three examples of homomorphisms that people usually see before learning the term “homomorphism.”

Exponential

For example, the function f(x) = ex is a homomorphism where * stands for addition of real numbers on the left and multiplication of positive real numbers on the right. That is,

ex+y = ex ey.

In words, the exponential of a sum is the product of exponentials.

Determinants

Another example of a homomorphism is determinant. Let A and B be two n by n matrices. Then

det(AB) = det(A) det(B).

In words, the determinant of a product is the product of determinants. But “product” refers to two different things in the previous sentence. The first product is a matrix product and the second product is a product of real numbers.

Fourier transform

One last example of a homomorphism is the Fourier transform F. It satisfies

F(f * g) = F(f) F(g)

where the group operation * on the left is convolution. In words, the Fourier transform of the convolution of two functions is the product of their Fourier transforms.

Homomorphic encryption

Homomorphic encryption is an encryption algorithm that is also a homomorphism. It allows the recipient of encrypted data to encrypt the result of some computation without knowing the inputs. I give three examples below.

Simple substitution

Here’s a trivial example. Suppose you have a simple substitution cipher, i.e. ever letter is simply replaced by some other letter. This is homomorphic encryption where the group operation is string concatenation [1]. If you encrypt two unknown words as xxw and jkh, I know that the encrypted form of the two words stuck together is xxwjkh.

A block cipher like AES is also homomorphic with respect to concatenation, if implemented naively. That is,

E(A + B) = E(A) + E(B)

where + means concatenation. The encrypted form of the concatenation of two blocks is the concatenation of the two blocks encrypted separately.

The approach is called Electronic Code Book or ECB mode. It’s never used in practice. Instead, you might use something like Cipher Block Chaining, CBC mode. Here the encrypted form of one block is XOR’d with the next clear block before encrypting it. [2]

An important point here is that when we say an encryption method is homomorphic, we have to say what operations its homomorphic with respect to. Being homomorphic with respect to concatenation is not useful, and is in fact a weakness.

Goldwasser-Micali

A non-trivial example is the Goldwasser-Micali algorithm. If you’re given the encrypted form of two bits, you can compute an encrypted form of the XOR of the two bits without knowing the value of either bit. Specifically, bits are encoded as large numbers modulo a public key. If c1 and c2 are encrypted forms of bits b1 and b2, then c1 c2 is an encrypted form of

b1 ⊕ b2.

The same bit can be encrypted many different ways, so this isn’t a homomorphism in the simplest mathematical sense. That’s why I said “an encrypted form” rather than “the encrypted form.” This is common in homomorphic encryption.

Paillier

The Paillier encryption algorithm is something like RSA, and is homomorphic with respect to addition of messages. That is, if you encrypt two messages, m1 and m2, and multiply the results, you get something that decrypts to m1 + m2. Here the addition and multiplication are modulo some large integer.

As with the G-M algorithm above, encryption is not unique. Decryption is unique, but there’s a random choice involved in the encryption process. The recipient of the encoded data is able to compute an encrypted form of their sum.

The Paillier algorithm lets you encrypt two numbers and have someone securely add them for you without learning what the two numbers were. That doesn’t sound very exciting in itself, but it’s a useful building block for more useful protocols. For example, you may want to let someone carry out statistical calculations on private data without letting them see the data itself.

Related

[1] Strings with concatenation don’t form a group because there are no inverses. So technically we have a homomorphism of semigroups, not groups.

[2] There’s a famous example of the weakness of ECB mode using the Linux penguin logo. If you encrypt the logo image using ECB mode, you can still recognize the penguin in the encrypted version since repetitive parts of the original image correspond to repetitive parts of the encrypted image. If you use CBC mode, however, the encrypted image becomes white noise.

Encrypted Linux logo

Notes on computing hash functions

Posted on by John

A secure hash function maps a file to a string of bits in a way that is hard to reverse. Ideally such a function has three properties:

  1. pre-image resistance
  2. collision resistance
  3. second pre-image resistance

Pre-image resistance means that starting from the hash value, it is very difficult to infer what led to that output; it essentially requires a brute force attack, trying many inputs until something hashes to the given value.

Collision resistance means its extremely unlikely that two files would map to the same hash value, either by accident or by deliberate attack.

Second pre-image resistance is like collision resistance except one file is fixed. A second pre-image attack is harder than a collision attack because the attacker can only vary one file.

This post explains how to compute hash functions from the Linux command line, from Windows, from Python, and from Mathematica.

Files vs strings

Hash functions are often applied to files. If a web site makes a file available for download, and publishes a hash value, you can compute the hash value yourself after downloading the file to make sure they match. A checksum could let you know if a bit was accidentally flipped in transit, but it’s easy to deliberately tamper with files without changing the checksum. But a secure hash function makes such tampering unfeasible.

You can think of a file as a string or a string as a file, but the distinction between files and strings may matter in practice. When you save a string to a file, you might implicitly add a newline character to the end, causing the string and its corresponding file to have different hash values. The problem is easy to resolve if you’re aware of it.

Another gotcha is that text encoding matters. You cannot hash text per se; you hash the binary representation of that text. Different representations will lead to different has values. In the examples below, only Python makes this explicit.

openssl digest

One way to compute hash values is using openssl. You can give it a file as an argument, or pipe a string to it.

Here’s an example creating a file f and computing its SHA256 hash.

    $ echo "hello world" > f
    $ openssl dgst -sha256 f
    SHA256(f)= a948904f2f0f479b8f8197694b30184b0d2ed1c1cd2a1ec0fb85d299a192a447

We get the same hash value if we pipe the string “hello world” to openssl.

    $ echo "hello world" | openssl dgst -sha256
    a948904f2f0f479b8f8197694b30184b0d2ed1c1cd2a1ec0fb85d299a192a447

However, echo silently added a newline at the end of our string. To get the hash of “hello world” without this newline, use the -n option.

    $ echo -n "hello world" | openssl dgst -sha256
    b94d27b9934d3e08a52e52d7da7dabfac484efe37a5380ee9088f7ace2efcde9

To see the list of hash functions openssl supports, use list --digest-commands. Here’s what I got, though the output could vary with version.

    $ openssl list --digest-commands
    blake2b512 blake2s256 gost     md4
    md5        mdc2       rmd160   sha1
    sha224     sha256     sha3-224 sha3-256
    sha3-384   sha3-512   sha384   sha512
    sha512-224 sha512-256 shake128 shake256
    sm3

A la carte commands

If you’re interested in multiple hash functions, openssl has the advantage of handling various hashing algorithms uniformly. But if you’re interested in a particular hash function, it may have its only command line utility, such as sha256sum and md5sum. But these are not named consistently. For example, the utility to compute BLAKE2 hashes is b2sum.

hashalot

The hashalot utility is designed for hashing passphrases. As you type in a string, the characters are not displayed, and the input is hashed without a trailing newline character.

Here’s what I get when I type “hello world” at the passphrase prompt below.

    $ hashalot -x sha256
    Enter passphrase:
    b94d27b9934d3e08a52e52d7da7dabfac484efe37a5380ee9088f7ace2efcde9

The -x option tells hashalot to output hexadecimal rather than binary.

Note that this produces the same output as

    echo -n "hello world" | openssl dgst -sha256

According to the documentation,

    Supported values for HASHTYPE:
    ripemd160 rmd160 rmd160compat sha256 sha384 sha512

Python hashlib

Python’s hashlib library supports several hashing algorithms. And unlike the examples above, it makes the encoding of the input and output explicit.

    import hashlib
    print(hashlib.sha256("hello world".encode('utf-8')).hexdigest())

This produces b94d…cde9 as in the examples above.

hashlib has two attributes that let you know which algorithms are available. The algorithms_available attribute is the set of hashing algorithms available in your particular instance, and the algorithms_guaranteed attribute is the set of algorithm guaranteed to be available anywhere the library is installed.

Here’s what I got on my computer.

    >>> a = hashlib.algorithms_available
    >>> g = hashlib.algorithms_guaranteed
    >>> assert(g.issubset(a))
    >>> g
    {'sha1', 'sha512', 'sha3_224', 'shake_256', 
     'sha3_256', 'sha256', 'shake_128', 'sha224', 
     'md5', 'sha384', 'blake2s', 'sha3_512', 
     'blake2b', 'sha3_384'}
   >>> a.difference(g)                                                             
   {'md5-sha1', 'mdc2', 'sha3-384', 'ripemd160', 
    'blake2s256', 'md4', 'sha3-224', 'whirlpool', 
    'sha512-256', 'blake2b512', 'sha512-224', 'sm3', 
   'shake128', 'shake256', 'sha3-512', 'sha3-256'}

Hashing on Windows

Windows has a utility fciv whose name stands for “file checksum integrity verifier”. It only supports the broken hashes MD5 and SHA1 [1].

PowerShell has a function Get-FileHash that uses SHA256 by default, but also supports SHA1, SHA384, SHA512, and MD5.

Hashing with Mathematica

Here’s our running example, this time in Mathematica.

    Hash["hello world", "SHA256", "HexString"]

This returns b94d…cde9 as above. Other hash algorithms supported by Mathematica: Adler32, CRC32, MD2, MD3, MD4, MD5, RIPEMD160, RIPEMD160SHA256, SHA, SHA256, SHA256SHA256, SHA384, SHA512, SHA3-224, SHA3-256, SHA3-384, SHA3-512, Keccak224, Keccak256, Keccak384, Keccak512, Expression.

Names above that concatenate two names are the composition of the two functions. RIPEMD160SHA256 is included because of its use in Bitcoin. Here “SHA” is SHA-1. “Expression” is a non-secure 64-bit hash used internally by Mathematica.

Mathematica also supports several output formats besides hexadecimal: Integer, DecimalString, HexStringLittleEndian, Base36String, Base64Encoding, and ByteArray.

Related posts

[1] It’s possible to produce MD5 collisions quickly. MD5 remains commonly used, and is fine as a checksum, though it cannot be considered a secure hash function any more.

Google researchers were able to produce SHA1 collisions, but it took over 6,000 CPU years distributed across many machines.

Making public keys factorable with Rowhammer

Posted on by John

The security of RSA encryption depends on the fact that the product of two large primes is difficult to factor. So if p and q are large primes, say 2048 bits each, then you can publish n = pq with little fear that someone can factor n to recover p and q.

But if you can change n by a tiny amount, you may make it much easier to factor. The Rowhammer attack does this by causing DRAM memory to flip bits. Note that we’re not talking about breaking someone’s encryption in the usual sense. We’re talking about secretly changing their encryption to a system we can break.

To illustrate on a small scale what a difference changing one bit can make, let p = 251 and q = 643.  Then n = pq = 161393. If we flip the last bit of n we get m = 161392. Although n is hard to factor by hand because it has no small factors, m is easy to factor, and in fact

161392 = 24 × 7 × 11 × 131.

For a larger example, I generated two 100-bit random primes in Mathematica

p = 1078376712338123201911958185123
q = 1126171711601272883728179081277

and was able to have it factor n = pq in about 100 seconds. But Mathematica was able to factor n-1 in a third of a second.

So far we have looked at flipping the least significant bit. But Rowhammer isn’t that precise. It might flip some other bit.

If you flip any bit of a product of two large primes, you’re likely to get an easier factoring problem, though the difficulty depends on the number you start with and which bit you flip. To illustrate this, I flipped each of the bits one at a time and measured how long it took to factor the result.

The median time to factor n with one bit flipped was 0.4 seconds. Here’s a plot of the factoring times as a function of which bit was flipped.

factoring times for corrupted product of primes

The plot shows about 80% of the data. Twenty percent of the time the value was above 11 seconds, and the maximum value was 74 seconds. So in every case flipping one bit made the factorization easier, usually quite a lot easier, but only a little easier in the worst case.

To verify that the results above were typical, I did a second experiment. This time I generated a sequence of pairs of random 100-bit primes. I factored their product, then factored the product with a randomly chosen bit flipped. Here are the factoring times in seconds.

    |----------+---------|
    | Original | Flipped |
    |----------+---------|
    |  117.563 |   3.828 |
    |  108.672 |   4.875 |
    |   99.641 |   0.422 |
    |  103.031 |   0.000 |
    |   99.188 |   0.000 |
    |  102.453 |   0.234 |
    |   79.594 |   0.094 |
    |   91.031 |   0.875 |
    |   64.313 |   0.000 |
    |   95.719 |   6.500 |
    |  131.125 |   0.375 |
    |   97.219 |   0.000 |
    |   98.828 |   0.203 |
    |----------+---------|

By the way, we started this post by talking about maliciously flipping a bit. The same thing can happen without a planned attack if memory is hit by a cosmic ray.

Related posts

Using one RNG to sample another

Posted on by John

Suppose you have two pseudorandom bit generators. They’re both fast, but not suitable for cryptographic use. How might you combine them into one generator that is suitable for cryptography?

Coppersmith et al [1] had a simple but effective approach which they call the shrinking generator, also called irregular decimation. The idea is to use one bit stream to sample the other. Suppose the two bit streams are ai and bi. If ai = 1, then output bi. Otherwise, throw it away. In NumPy or R notation, this is simply b[a > 0].

Examples in Python and R

For example, in Python

    >>> import numpy as np
    >>> a = np.array([1,0,1,1,0,0,0,1])
    >>> b = np.array([1,0,1,0,0,1,1,0])
    >>> b[a > 0]
    array([1, 1, 0, 0])

Here’s the same example in R.

    > a = c(1,0,1,1,0,0,0,1)
    > b = c(1,0,1,0,0,1,1,0)
    > b[a>0]
    [1] 1 1 0 0

Linear Feedback Shift Registers

Coppersmith and colleagues were concerned specifically with linear feedback shift register (LFSR) streams. These are efficient sources of pseudorandom bits because they lend themselves to hardware implementation or low-level software implementation. But the problem is that linear feedback shift registers are linear. They have an algebraic structure that enables simple cryptographic attacks. But the procedure above is nonlinear and so less vulnerable to attack.

A potential problem is that the shrinking generator outputs bits at an irregular rate, and a timing attack might reveal something about the sampling sequence a unless some sort of buffering conceals this.

Other stream sources

While the shrinking generator was developed in the context of LFSRs, it seems like it could be used to combine any two PRNGs in hopes that the combination is better than the components. At a minimum, it doesn’t seem it should make things worse [2].

There is a problem of efficiency, however, because on average the shrinking generator has to generate 4n bits to output n bits. For very efficient generators like LFSRs this isn’t a problem, but it could be a problem for other generators.

Self-shrinking generators

A variation on the shrinking generator is the self-shrinking generator. The idea is to use half the bits of a stream to sample the other half. Specifically, look at pairs of bits, and if the first bit is a 1, return the second bit. If the first bit is a 0, return nothing.

Use in stream ciphers

The eSTREAM competition for cryptographically secure random bit generators included one entry, Decim v2, that uses shrinking generators. The competition had two categories, methods intended for software implementation and methods intended for hardware implementation. Decim was entered in the hardware category. According to the portfolio PDF [3] on the competition site,

Decim contains a unique component in eSTREAM, that of irregular decimation, and is an interesting addition to the field of stream ciphers.

That sounds like it was the only method to use irregular decimation (i.e. shrinking generators).

The first version of Decim had some flaws, but the document says “no adverse cryptanalytic results are known” for the second version. Decim v2 made it to the second round of the eSTREAM competition but was not chosen as a finalist because

… the cipher doesn’t seem to deliver such a satisfying performance profile, so while there might be some very interesting elements to the Decim construction, we feel that the current proposal doesn’t compare too well to the other submissions for the hardware profile.

That seems to imply Decim might be competitive with a different implementation or in some context with different trade-offs.

Related posts

[1] Coppersmith, D. Krawczyk, H. Mansour, Y. The Shrinking Generator. Advances in Cryptology — CRYPTO ’93. Lecture Notes in Computer Scienc, vol. 773, pp. 22–39. Springer, Berlin.

[2] If a and b are good sources of random bits, it seems b sampled by a should be at least as good. In fact, if a is poor quality but b is good quality, b sampled by a should still be good. However, the reverse could be a problem. If b is biased, say it outputs more 1s than 0s, then if a is a quality sample, that sample will be biased in favor of 1s as well.

[3] The link to this report sometimes works but often doesn’t. There’s something unstable about the site. In case it works, here’s the URL: http://www.ecrypt.eu.org/stream/portfolio.pdf

Inside the AES S-box

Posted on by John

The AES (Advanced Encryption Standard) algorithm takes in blocks of 128 or more bits [1] and applies a sequence of substitutions and permutations. The substitutions employ an “S-box”, named the Rijndael S-box after its designers [2], an invertible nonlinear transformation that works on 8 bits at a time.

There are 256 = 16 × 16 possible 8-bit numbers, and so the S-box can be represented as a 16 by 16 table mapping inputs to outputs. You can find the tables representing the S-box and its inverse in this text file in org-mode format.

This post will look in detail at how the entries of that table are filled. A high-level description of the design is as follows. For an 8-bit number x,

  1. Invert in GF(28)
  2. Multiply by a matrix L
  3. Add a constant c.

Next we dive into what each of these steps mean. And at the end we’ll work an example in detail.

My source is The Block Cipher Companion by Knudsen and Robshaw.

Inversion in GF(28)

Steps 1 and 3 take the inverse of a number as a member of the finite field GF(28), a finite field with 28 elements.

The number of elements in a finite field determines the field, up to isomorphism. That is, in a sense there is only one field with 28 = 256 elements. In fact there are 30 different fields with 256 elements (see this post for where that number came from). The 30 fields are isomorphic, but when we’re doing actual calculations, rather than abstract theory, we need to specify which representation we’re using.

Finite fields can be specified as polynomials modulo an irreducible polynomial. To carry out our calculations we need to specify a particular irreducible 8th degree polynomial with binary coefficients. The one that AES uses is

p(x) = x8 + x4 + x3 + x + 1.

So by taking the inverse in GF(28) we mean to take an 8-bit number y, interpret it as a polynomial with binary coefficients, and find another 8-bit number x-1 such that when we multiply them as polynomials, and take the remainder after dividing by p(x) we get the polynomial 1.

There’s one wrinkle in this procedure: only 255 of the 256 elements of GF(28) have an inverse. There is no inverse for 0, but for our purposes we’ll take the inverse of 0 to be 0.

Multiplication by L

The matrix L we need here is the 8 by 8 binary matrix whose entries are

        10001111
        11000111
        11100011
        11110001
        11111000
        01111100
        00111110
        00011111

When we say to multiply x-1 by L we mean to think of x-1 as a vector over the field of two elements, and carry out matrix multiplication in that context.

Additive constant

The constant that we add is 0x63. The reason an additive constant was chosen was so that a zero input would not map to a zero output. Note that “addition” here is vector addition, and is carried out over the field of two elements, just as the multiplication above. This amounts to XOR of the bits.

Manual calculation example

To make everything above more concrete, we’ll calculate one entry of the table by hand.

Lets start with input y = 0x11 = 0b10001. We represent y as the polynomial f(x) = x4 + 1 and look for a polynomial g(x) such that the remainder when f(x) g(x) is divided by p(x) defined above is 1.

The process of finding g is complicated—maybe I’ll blog about it in the future—but I claim

g(x) = x7 + x5 + x4 + x2

which means the inverse of y in GF(28), represented in binary, is 0b10110100 = 0xB4. You can find a table of inverses here.

Next we multiply the matrix L by the vector made from the bits of y-1. However, there is a gotcha here. When Knudsen and Robshaw say to multiply the bits of y-1 by L, they assume the bits are arranged from least significant to most significant. Since the bits of y-1 are 10110100, we multiply L by the vector

[0, 0, 1, 0, 1, 1, 0, 1].

This multiplication gives us the vector

[1, 0, 0, 0, 0, 1, 1, 1].

Next we add the vector formed from the bits of 0x63, again from least significant to most significant. That means we lay out 0x63 = 0b01100011 as

[1, 1, 0, 0, 0, 1, 1, 0].

This gives us the result

[0, 1, 0, 0, 0, 0, 0, 1].

Reading the bits from least significant to most, this gives 0x82.

In sum, we’ve verified that the AES S-box takes 0x11 to 0x82, as stated in the table.

Related posts

[1] The Rijndael block cipher operates on blocks whose size is a multiple of 32 bits. The AES standard adopted Rijndael with block sizes 128, 192, and 256.

[2] “Rijndael” is a play on the designers of the cipher, Vincent Rijmen and Joan Daemen.