4
$\begingroup$

I'm designing a cryptography assignment for a college security course, and one of the problems is to perform a simple meet-in-the-middle attack on a 2-round, 2-key cipher.

Since we want this to be a reasonable attack for students to mount on their own laptops or school computers, the cipher needs to be very fast to compute. However, all of the ciphers I've looked at so far require significant key expansion via a key schedule, and since each encryption/decryption performed is with a different key, this expansion must be performed for every encryption/decryption operation, which we're finding in practice has a big performance penalty.

What I'm wondering is: are there any block ciphers that don't use key expansion?

These don't have to be secure by any stretch of the imagination: just secure enough that it's easier for students to do the assignment directly than break the block cipher via some other means.

| improve this question | |
$\endgroup$
  • $\begingroup$ Block-ciphers designed as core of hash functions have cheap key setup (but often large key and/or block size). For example three-fish in its 256 bit variant could be a viable choice. $\endgroup$ – CodesInChaos Oct 27 '15 at 16:14
  • $\begingroup$ I don't understand why you need to avoid the key schedule. The implementation of the meet-in-the-middle attack can ignore the key schedule and treat the cipher as if it has two independently keyed round subkeys. (Alternatively, you could rip out the key schedule and use independent round subkeys as part of the cipher spec.) So I can't understand where the question is coming from. $\endgroup$ – D.W. Oct 27 '15 at 16:31
  • $\begingroup$ @D.W. I think it's about the key setup cost of the two individual ciphers. $\endgroup$ – CodesInChaos Oct 27 '15 at 16:35
  • $\begingroup$ @CodesInChaos, Huh. Confusing. The question doesn't mention anything about two individual ciphers. In contrast, it does mention a 2-round cipher (which would be natural to apply a MITM attack to, on its own, without needing another cipher for the exercise to make sense). Puzzling. $\endgroup$ – D.W. Oct 27 '15 at 16:38
  • $\begingroup$ Yes, the concern is about the computation cost of computing the key schedule. Since we try a different key each time, the key schedule must be recomputed every time. $\endgroup$ – joshlf Oct 27 '15 at 16:39
6
$\begingroup$

You might consider using TEA or its successor, XTEA. Here's the complete C source code for XTEA, taken from the Wikipedia article:

#include <stdint.h>

/* take 64 bits of data in v[0] and v[1] and 128 bits of key[0] - key[3] */

void encipher(unsigned int num_rounds, uint32_t v[2], uint32_t const key[4]) {
    unsigned int i;
    uint32_t v0=v[0], v1=v[1], sum=0, delta=0x9E3779B9;
    for (i=0; i < num_rounds; i++) {
        v0 += (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + key[sum & 3]);
        sum += delta;
        v1 += (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + key[(sum>>11) & 3]);
    }
    v[0]=v0; v[1]=v1;
}

void decipher(unsigned int num_rounds, uint32_t v[2], uint32_t const key[4]) {
    unsigned int i;
    uint32_t v0=v[0], v1=v[1], delta=0x9E3779B9, sum=delta*num_rounds;
    for (i=0; i < num_rounds; i++) {
        v1 -= (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + key[(sum>>11) & 3]);
        sum -= delta;
        v0 -= (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + key[sum & 3]);
    }
    v[0]=v0; v[1]=v1;
}

This code is simple enough that your students should be able to easily integrate it into their programs, and even modify it if necessary. You might even want to consider reusing it for other exercises, too. Notably, it also involves no special pre-processing of the key — the "key schedule", such as it is, is very simple and done directly within the encryption loop.

One feature of (X)TEA that (while generally a good thing) may not be ideal for your purposes is that it has a 128-bit keyspace, which is too large for a practical brute force search. For your exercise, you could artificially restrict the keyspace to just, say, 32 bits by setting the remaining 96 bits of the key to some fixed value. Then compositing two such encryptions with different keys should give you a 64-bit keyspace, which is still rather large to just exhaustively search by brute force, whereas the meet-in-the-middle attack needs only up to 233 operations, which should be easily doable.

By the way, the general property you're asking for is called key agility. You may find other suitable ciphers by Googling for "key-agile cipher".

| improve this answer | |
$\endgroup$

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.