33
$\begingroup$

Inspired by Magic "Nothing Up My Sleeve" Numbers - Computerphile - YouTube [5:31]. If you just need a constant to begin your algorithm, and the value of that constant isn't important, why not have a widely known convention to always use the digits of Pi or Phi or other well known constant? It would seem that choosing arbitrary numbers is bad because it causes doubt as to the origin of the numbers which may lead some to suspect they were cherry picked for undisclosed weaknesses.

$\endgroup$
  • $\begingroup$ This is actually done quite often, however it doesn't always yield the best properties which is why sometimes constants are picked in some other manner, eg by running a well-defined, deterministic program that finds constants that exhibit the desired properties the most. $\endgroup$ – SEJPM Apr 19 '17 at 15:31
  • 13
    $\begingroup$ The BADA55 paper comes to mind. $\endgroup$ – yyyyyyy Apr 19 '17 at 15:38
  • $\begingroup$ @SEJPM What you wrote feels like "Yes the fact that putting magic numbers is often done to create weaknesses." but I also get that you actually mean choosing a well known number. $\endgroup$ – Etherealone Apr 25 '17 at 20:52
19
$\begingroup$

If you just need a constant to begin your algorithm, and the value of that constant isn't important, why not have a widely known convention to always use the digits of Pi or Phi or other well known constant?

Why not use all zeros or all ones then? Why not use what user provided us with?

There is a joke: Good thing about standards is that we have so many to choose from.

Often there are some values that are supposed to have specific properties, like being prime numbers. Then you have to use CSPRNG with that constant. Why not use this CSPRNG, why not that one. This one is simple, this one is more secure, this is newer, this is more well-established etc.

In short: because they are used in widely different settings, and we usually have some vague requirements:

  • Sometimes it has to be of any length and secure (DH safe prime generation)
  • Sometimes it has to be of any length and just simple constant (HMAC)
  • Sometimes it has to be specific length and have high entropy (AES)
  • Sometimes it has to be fairly independent from another constant we used somewhere else

Last requirement is probably worst. There might be interference from two different algorithms that happen to use same constant, and since you have one standard you increase such possibility.

Even if you managed to fulfill that somehow, some values are supposed to have high entropy, and some can be plain anything. Making them meaningful decreases speed your algorithm will work on.

All that and you gain that 1% extra security that nobody did plant bug in algorithm. Sadly IMO this doesn't give us much and prevents smart designs that are faster while retaining security.

|improve this answer|||||
$\endgroup$
  • 5
    $\begingroup$ Can you define what you mean by "entropy"? The constants have 0 entropy in as much as their values are publicly known by everyone. Did you mean something like the complexity of the string? $\endgroup$ – Ella Rose Apr 19 '17 at 18:45
  • $\begingroup$ @EllaRose true, i meant how random-looking they are. HMAC has simply 6C6C6C... and AES constants are looking fairly random. Let's call that how uncompressable they are :). If you have idea how to call that neatly please edit $\endgroup$ – axapaxa Apr 19 '17 at 19:11
  • 5
    $\begingroup$ @EllaRose we might not be able to assign a reasonable value for entropy, but we might be able to assign a value for Komolgorov complexity $\endgroup$ – k_g Apr 19 '17 at 21:37
  • 8
    $\begingroup$ @k_g, but the point of "nothing up my sleeve" answers is to have low Kolmogorov complexity: that's how you show that there's nothing up your sleeve. $\endgroup$ – Peter Taylor Apr 20 '17 at 8:24
  • $\begingroup$ @axapaxa The HMAC ipad and opad values are not nothing-up-my-sleeve numbers. They were chosen so $k \oplus \mathrm{opad} \ne k \oplus \mathrm{ipad}$. Any constants that differ significantly would work. Their only requirements were to be simple (to reduce complexity in defining the specification and make implementation errors less likely) and to provide a high Hamming distance between the resulting keys so that they are both computationally independent. This is described in section 5.2 of the paper introducing HMAC. $\endgroup$ – forest Aug 7 '18 at 1:41
12
$\begingroup$

If you just need a constant to begin your algorithm, and the value of that constant isn't important, why not have a widely known convention to always use the digits of Pi or Phi or other well known constant?

This is a fantastic question that I feel should be directed towards every cipher/permutation proposal. I am not able to find a research paper which suggests exactly what convention should be used, and so people are probably still rolling their own ad-hoc methods for generating constants.

I am not aware of an official standard, but a widely accepted convention appears to be selecting some innocuous numbers (i.e. pi, phi, square roots of numbers, etc) then running some kind of function on them to extract output. The function in question might be as simple as selecting certain bits of the supplied number. This appears to be more or less a de facto standard way of generating constants.

Assuming a symmetric primitive, I personally advocate applying the linear layer of the primitive to an incrementing counter to generate constants.

The reason why is because it removes any degrees of freedom in generating constants, since it is always done the same with with no choice/input from the designer (i.e. me). There are no degrees of freedom if you can assume the linear layer was designed to generate highly different outputs and not designed to generate secretly weak output/malicious constants (which would probably cripple the rest of the design).

Additionally, it re-uses the resources that are already available: It requires less data (no tables of constants), which means lower storage requirements, fewer register swaps, as well as less code.

|improve this answer|||||
$\endgroup$
9
$\begingroup$

Ostensibly, there is a convention for constants. It's vanity.

The criteria for such a constant is to disassociate the number from any possible influence it might have on the algorithm. Yes, high entropy is useful sometimes, but most of time any number will do. An analysis hasn't been performed, but the SHA1 constants probably would work just as well if they were 12345... But no one would trust that they weren't secretly selected to have some deleterious effect on security. So you pick square roots, or something related to primes as for SHA2. Anything really as long as it is extremely apparent and beyond any possible doubt that it cannot be related to the operation of the algorithm.

If you've spent five years creating the next big cryptographic thing, you'll be tempted to show off with a novel method for constant creation. And it has to meet the disassociation requirements above. So what to do? All the simple roots have been used, as have (most) of the digits of π. The antithesis of secret collusion must be publicly generated numbers, and so the Million Dollar Elliptic curve constants use lottery numbers. I'm not a professional cryptographer, so I cannot judge how this showmanship is received by the community. SHA256 uses 256 bytes of constants. I'm sure that the function would be just as secure if those 256 bytes were the first 256 letters in ASCII form from A Midsummer Night's Dream. It is mathematically improbable that text could be somehow related to the SHA256 bit manipulations thereby satisfying disassociation.

You have to realise that cryptographers are real people with all the human traits. We all show off sometimes.

|improve this answer|||||
$\endgroup$
  • 2
    $\begingroup$ Actually the SHA-1 initial state is [0x67452301, 0xEFCDAB89, 0x98BADCFE, 0x10325476, 0xC3D2E1F0], which is not unlike 12345. On the other hand, SHA-2 initial states use digits of irrational numbers. $\endgroup$ – Nayuki Apr 20 '17 at 3:55
  • $\begingroup$ Reusing the same constants used in other algorithms would be suspicious? You can also get constants from the hashes of simple strings, like the null hash of SHA-256. You could generate S-boxes, for instance, using the Fisher-Yates shuffle and the output of AES run in counter mode with an all-zero key. $\endgroup$ – Melab Sep 22 '17 at 15:11
  • $\begingroup$ @Melab Yes you can absolutely reuse constants from other primitives, but vanity probably wouldn't allow it. If you've spent 2 years designing a replacement for AES, you can't really cop out and use pi can you? You need to show flair and imagination, and it really doesn't matter how wild you go as long as dissociation is served. $\endgroup$ – Paul Uszak Sep 22 '17 at 17:58

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.