1
$\begingroup$

Why was such a weak key schedule chosen for IDEA?

The key schedule of IDEA works like this: Divide the key (128 bit) into 8 round keys, each 16 bit long. This are the first 8 "round" keys (6 keys per round). Rotate the original key by 25 bit to the left. Repeat this until we got the needed 52 round keys for 8.5 rounds. (4 keys for the last "half" round.) This key schedule is fully linear and patterns in the key exist even in the last round keys with nearly no change. A high number of zero bits in the key is very problematic for the cipher because the number stays the same through the whole key schedule. Many attacks exploit this behavior.

This can be seen with a small example encryption. (Key ($K$) and plaintext ($P$) in hexadecimal formatting, leading zero bytes were omitted. ) $$ K = 00, P = 00, \operatorname{IDEA}(K,P) = \text{0001 0001 0000 0000} $$ $$ K = 00, P = 01, \operatorname{IDEA}(K,P) = \text{0013 fff5 0012 0009} $$ $$ K = 00, P = 02, \operatorname{IDEA}(K,P) = \text{0191 0059 011c ff32} $$ $$ K = 00, P = 03, \operatorname{IDEA}(K,P) = \text{038f 0099 02d6 fe33} $$ $$ K = 00, P = \text{01f0}, \operatorname{IDEA}(K,P) = \text{1841 fbc1 ef20 f270} $$ $$ K = \text{0d50}, P = 00, \operatorname{IDEA}(K,P) = \text{3fb2 5ff2 055d 16a6} $$ (Source: IDEA calculator (Java))

Further analysis of the data and the encryption process shows very slow avalanche effect when high amount of zero bits were in the plaintext or ciphertext. Why was this not recognized and solved? Was this kind of problem not known at the time as IDEA was invented? Or is this no real problem because of the low probability of this effect on random keys?

The paper "Weak Keys for IDEA" (1993, PDF) shows that even a small correction could solves this problem, like the XOR of a constant to every round key before using it. The constant $\text{0dae}$ (16 bit, hexadecimal notation) was chosen as an example, but the exact value is not critical to solve the problem as stated by the paper.

Are there any papers which descripe the development process of IDEA? Maybe they could explain some thoughs about the key schedule.

Improve this question
$\endgroup$
6
  • $\begingroup$ How could anyone other than the designers of IDEA possibly answer this question with any degree of certainty? I suggest you edit the question to ask a technical question, one where answers can be supported by facts and reasoning and evidence, not a question that invites speculation (asks us to read the mind of the designers of IDEA). $\endgroup$
    – D.W.
    Oct 13, 2014 at 2:56
  • $\begingroup$ @D.W.: Maybe there's a paper with explanations of some of the design decisions, like for most algorithms of the AES competition. $\endgroup$
    – Nova
    Oct 13, 2014 at 3:05
  • $\begingroup$ Nova, well, OK, what research have you done? Have you searched on Google Scholar? If that's what you want to know, you could edit your question to ask "Is there a paper explaining the design decisions that went into IDEA?". But, truthfully, that's not a good question -- the answer is yes there's such a paper and you can find your own using Google Scholar, so asking such a question would be a poor question because it would indicate you haven't done your research. $\endgroup$
    – D.W.
    Oct 13, 2014 at 3:09
  • $\begingroup$ @D.W.: Searching for IDEA is not easy, because it was never the "main encryption algorithm" (the first was DES, then AES) and it was patented. Oh, and it was no good idea to name it IDEA (pun intended). Most results are for implementations of IDEA, not really analysis. In the moment I read "On the Design and Security of Block Ciphers" (e-collection.library.ethz.ch/eserv/eth:38650/eth-38650-02.pdf), but I can't find any explanations why exactly this schedule was chosen. $\endgroup$
    – Nova
    Oct 13, 2014 at 12:08
  • $\begingroup$ Nova, OK, I'm sympathetic. But the papers that describe the design of IDEA are cited in "Weak Keys for IDEA", which you link to in your post; see the introduction and references [1,2]. So, you can check for yourself whether the designers said anything on this topic in those papers. Are you familiar with how to do a literature search? $\endgroup$
    – D.W.
    Oct 13, 2014 at 15:26

1 Answer 1

Reset to default
5
$\begingroup$

Such a weak key schedule was chosen since the key schedule "theory" was not well developed by that time. Designers just modified the key schedule of DES a bit. Remember that these key schedules had to be optimized for hardware, and any extra operation would cost something in terms of area.

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ That looks like a good answer to me, but any references would be highly appreciated. $\endgroup$
    – Maarten Bodewes ♦
    Oct 9, 2014 at 12:44
  • 3
    $\begingroup$ This is my educated guess based on the evolution of block ciphers and contemporary theory. Serious block cipher research appeared later (for example, Daemen's PhD thesis from 1995). $\endgroup$
    – Dmitry Khovratovich
    Oct 11, 2014 at 11:53

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