13
$\begingroup$

A number of cryptographic functions have constants built in. For example, the constants used in RFC 2104 for HMAC, or the constants used in s-boxes (e.g., DES and AES), or MD5. In general, how are constants such as these generated so as not to arouse suspicion of tampering or weakening?

$\endgroup$
13
$\begingroup$

There are some approaches.

  • In many algorithms it for the security doesn't really matter what constant is used, as long as it is not too simple, like initialization vectors for hash functions. (And of course, we need to use always the same number.) Then mathematical constants like binary expansions of irrational numbers like $\sqrt{2}$ (or roots of other numbers), $e$, $\pi$ can be used, to show that one didn't select the numbers to create a back door. This is known as a nothing up my sleeve number, the linked Wikipedia article contains some more examples.

  • The padding constants for HMAC, 0x36 for ipad and 0x5C for opad, are repeated (for the hash function's block size) and XORed with the key to generate the prefixes for the two hashing steps. 0x36 = 0b00110110 and 0x5C = 0b01011100 - these two values are about "as different as possible", to avoid any attacks which rely on a similar hash state after the key block for inner and outer hash. This is mainly a heuristic, as far as I understand.

  • In the DES S-boxes, the constants were randomly generated and then tested for resistance against differential cryptanalysis. As differential cryptanalysis was not yet known officially, and NSA didn't explain what they did (one only could see that they gave it back with other S-boxes), there was quite some suspicion that they put in a backdoor, while they actually made the algorithm harder to break.

  • In AES, the S-boxes are an implementation of a simple mathematical function (inversion in $\mathbb F_{2^8}$, followed by a linear transformation). One wouldn't need an S-box here, it just helps to efficiently implement it.

  • In the hash function Skein (one of the SHA-3 candidates), the initialization vector (initial state of the iteration) is not a fixed arbitrary number, but is gained by hashing a "configuration vector" (where we use 0 as init state). If one uses Skein only in common uses (e.g. a simple hash), i.e. always with the same configuration, one can hardcode the resulting hash state into the implementation instead of re-running it each time.

$\endgroup$
  • 6
    $\begingroup$ As to 0x36 and 0x5c: the requirement for these constants is that there are 4 types of bit positions in a byte: where both constants have 0-bits, both have 1-bits, constant1 has a 1 and constant2 a 0, and vice versa. This means that (when we xor this with a key byte) we toggle half the key bits every time. The security proof depends on the constants having these properties, IIRC. $\endgroup$ – Henno Brandsma Nov 7 '11 at 18:22
  • 3
    $\begingroup$ As to S-boxes: there was already a theorem proven that inversion in a field is almost optimally non-linear in a certain sense, and this was the reason the transform was used; the affine transform afterwards is to get rid of the fix point 0 --> 0. The precise form of the constants in the S-box then follows directly from the polynomial in the definition of the Galois field. $\endgroup$ – Henno Brandsma Nov 7 '11 at 18:25
  • 2
    $\begingroup$ @Henno: Do you have some link for the HMAC-proof? I had a look at New Proofs for NMAC and HMAC: Security without Collision-Resistance, but this proof seems to work with any values of ipad and opad. $\endgroup$ – Paŭlo Ebermann Nov 7 '11 at 19:01
  • $\begingroup$ it seems to be that this is hidden in the rka-advantage used in the bound of lemma 5.2 of that paper (the original Crypto 96 paper, to which I do not have access right now, might have more info, and could be my source of recollection); the homogeneity property that I mentioned might give a sharper security bound; and I cannot think the constants are irrelevant, I'd think that constants 0 and 0xff would give worse results, intuitively. $\endgroup$ – Henno Brandsma Nov 7 '11 at 19:26
  • 1
    $\begingroup$ It does contain this paragraph: The above particular values of opad and ipad were chosen to have a very simple representation (to simplify the function's specification and minimize the potential of implementation errors), and to provide a high Hamming distance between the pads. The latter is intended to exploit the mixing properties attributed to the compression function underlying the hash schemes in use. These properties are important in order to provide computational independence between the two derived keys. $\endgroup$ – Paŭlo Ebermann Nov 7 '11 at 19:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.