1
$\begingroup$

For example, this:

enter image description here

Are all those numbers like 7, 4, 13, 1, 10, 6, 15, 3, 12, 0, 9, 5, 2, 14, 11, 8... picked by hand somehow, or are they just selected out of a hat (like you write a script "give me 64 random integers between 0 and 15" and then whatever it outputs you use), or something else? What is the technique for selecting so many numbers?

$\endgroup$
2

1 Answer 1

3
$\begingroup$

Generally no. In cryptography, the appearance of "random" strings of numbers is generally quite suspect --- what if there are certain "weak" choices of numbers that yield the entire construction insecure? How do you know the designer didn't use their freedom in choosing these numbers to embed a backdoor? Note that this does happen, famous examples are:

Note that there are certain "arbitrary constants" that are seen as less suspect --- common choices are the digits of $\pi$, or things of this sort (say the digits of $\sqrt{2}$ or $\sqrt{3}$). These are often called nothing up my sleeve numbers, and can be reached for when the designer just needs some arbitrary numbers that satisfy some minimal constraints that "most" numbers should satisfy.

Anyway, returning to RIPEMD. It was initially specified in the 1995 paper "Integrity primitives for secure information systems." (I found this info via this link). In particular, the specification is contained in this document. I draw your attention to page 75 of the document (on page 7 of the pdf).

The four constants used in these operations are not randomly chosen; they are the integer part of $2^{30}\sqrt{2}, 2^{30}\sqrt{3}, 2^{30}\sqrt[3]{2}, 2^{30}\sqrt[3]{3}$ respectively. However, there is no specific reason for this choice.

This explains the constants in the added constants part of the file you linked --- they are nothing up my sleeve numbers. Unfortunately, the particular table you ask about is not satisfactorily explained. The authors state that they reproduce a modification of the compression function of MD4 (including the table you noticed), but simply state that they include modifications of B. den Boer, which they cite as Personal Communications (so their particular reason for the modification is unknown).

Unfortunately, other material on the cipher is not enlightening either. Consider this attack on the hash. The authors mention (as is readily apparent) that the "selection of message word" indices must specifically be a permutation (this was mentioned in the initial specification as well), but it is not clear why those particular permutations were chosen.

The last thing that I will mention is that sometimes you are in a situation where there are many possible choices of some structured object (like a permutation, so you cannot hope the digits of $\pi$ will suffice), and you need to pick one. One strategy you can do (rather than pulling it out of thin air) is:

  1. try to "rank" the structured objects according to some efficiency metric, and then
  2. choose the "first" (in some natural ordering) of the "most efficient" objects.

This is vague, so a particular example may be useful. The design of AES requires arithmetic over $\mathsf{GF}(2^8)$. Any irreducible degree 8 polynomial over $\mathbb{F}_2$ defines a "different" (but all mutually isomorphic) copy of $\mathsf{GF}(2^8)$. Given that this is the case, which polynomial do you choose in the design of AES?

The AES designers justify this choice (and others which you may find interesting) in section 7 of their proposal.

The polynomial $m(x)$ ... for the multiplication in $\mathsf{GF}(2^8)$ is the first one of the list of irreducible polynomials of degree 8, given in [LiNi86, p. 378].

So they appeal to some ordering by authors other than them. I have also seen (and thought I had for AES in particular) the choice to:

  1. collect all irreducible polynomials
  2. sort them by hamming weight (the efficiency metric)
  3. of those of minimal hamming weight, choose the lexicographically first one.

Of course, this is unfortunately not useful for your particular table.

$\endgroup$
6
  • $\begingroup$ Very interesting stuff, thank you so much! So in the end, what is the case with the numbers I listed, how were those (potentially) chosen? Never encountered the "nothing up my sleeve numbers", makes sense! $\endgroup$
    – Lance
    Jan 20 at 8:57
  • 1
    $\begingroup$ That's the somewhat annoying part for your particular numbers --- I can't track down the source for how they were generated. RIPEMD is a modification of MD4, specified here. The corresponding numbers for MD4 are different, and have some internal pattern that makes more sense. The RIPEMD authors state that they change these numbers, but only cite a personal communication (from 1992) with B. den Boer. Unfortunately, those personal communications likely have the answer to your question, but it seems unlikely to be able to find them published. $\endgroup$
    – Mark
    Jan 20 at 16:43
  • 1
    $\begingroup$ The only small comfort I have is that the published attack on RIPEMD I looked at completely ignored the (somewhat arbitrary) structure of your numbers, so it is plausible they don't meaningfully impact security at all, and they were modified for efficiency purposes on some platform (the RIPEMD authors spend a paragraph or two mentioning they're switching between little/big endian representations for this purpose). This is just a guess though, and without reaching out to B. den Boer (or the RIPEMD authors) it may be hard to get a better answer. $\endgroup$
    – Mark
    Jan 20 at 16:48
  • $\begingroup$ Kuznyechik: my understanding that, while the sbox is peculiar, and does not conform to the initial claims of randomness, there is still no (publicly) known backdoor based on it... $\endgroup$
    – poncho
    Jan 20 at 19:29
  • $\begingroup$ @poncho yes, but it has a very particular invariant that it maintains. Perhaps I have an alarmist reading of this, but I can't see a non-backdoor reason for this to be the case. $\endgroup$
    – Mark
    Jan 20 at 19:32

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.