4
$\begingroup$

I'm trying to follow Schneier's self-study course in cryptanalysis and am ashamed to say I am stuck on the very first problem of breaking 8-round RC5 without any rotations (i.e. just XOR and modular addition)...

I've obviously found the algorithm which can decrypt any ciphertext using only a handful of chosen plaintexts, by observing that the carries from addition only propagate one way so the plaintext can be brute-forced bit by bit starting from the least significant bit.

Now I'm trying to recover the subkeys, but am struggling, I've been spending nearly 6 days on it with no real progress... this is where I am at:

I tried some kind of backtracking search over the subkeys working from the LSB but it just fans out too quickly; there's 18 subkeys with 32 bits each, I can't get past 3 or 4 bits with this approach, and there doesn't seem to be any way to infer anything about distant subkey bits. I can't find any good linear approximation between plaintext and ciphertext bits beyond their least significant 4 bits or so...

I also found that if I tried to determine how often some linear relationships between the lowest plaintext and ciphertext bits hold for a given key and tried to guess the first few bits of each subkey based on these relationships I was able to glean some information about the first few bits of the very first subkey, but I don't see how to extend that.

Finally I noticed that the most significant bit of all subkeys but the last two are redundant; they can be folded in the last two subkeys since there is no carry. But this doesn't seem too helpful if I am to recover subkeys working from LSB to MSB.

My question is, was the exercise just about recovering the plaintext bypassing the key completely, or is there something utterly obvious that I'm not seeing that would allow to recover the subkeys efficiently? If there is, I need a hint or some pointers as I'm really completely stuck...

Thanks

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ What you have done is a break by most definitions, unambiguously including that in section 2 of the linked course. In fact, noticing that there is no right propagation and building a distinguisher out of that qualifies. But I agree that finding a key form plaintext/ciphertext pairs in the weakened RC5 is an interesting problem. Perhaps it can be solved by expressing the problem as a Boolean satisfiability problem and throwing that to a solver like CryptoMinisat. $\endgroup$
    – fgrieu ♦
    Commented Jan 27, 2020 at 11:17
  • $\begingroup$ @fgrieu yes I thought the trivial break was a little too... trivial so it seemed like there should be more, but this seems absurdly difficult. I did actually try to express the thing as a boolean satisfiability problem by encoding it in bitvecs and throwing it at Z3, I forgot that's one of the first things I did, it did a great job with two or three rounds but seems to be unable to handle it for 8 rounds. I'll take a look at cryptominisat though (maybe Z3's bitvec solver isn't geared for these sorts of reductions?) $\endgroup$
    – Seawaves32
    Commented Jan 27, 2020 at 11:19
  • $\begingroup$ My concern was more about whether I was missing something basic; if recovering the subkey is very nontrivial I'm more than happy to move on to the next exercise, but it would be good to have confirmation that it is hard, otherwise I'm just training myself to skip things that look hard... $\endgroup$
    – Seawaves32
    Commented Jan 27, 2020 at 13:13

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.