Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 9 down vote accepted

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.

share|improve this answer
3  
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. –  Henno Brandsma Nov 7 '11 at 18:22
2  
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. –  Henno Brandsma Nov 7 '11 at 18:25
1  
@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. –  Paŭlo Ebermann Nov 7 '11 at 19:01
    
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. –  Henno Brandsma Nov 7 '11 at 19:26
    
Looking at Keying hash functions for message authentication, which seems to be a fuller version of a paper which appeared in Crypto 96, there is no Lemma 5.2 (though section 5.2 is "Security of HMAC"). It doesn't contain any "rka-advantage". –  Paŭlo Ebermann Nov 7 '11 at 19:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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