public
Created

Example of meet-in-the-middle attack (in C)

  • Download Gist
meet.c
C
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132
/* Written by Dmitry Chestnykh. Public domain. */
#include <err.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>
#include <time.h>
#include <openssl/blowfish.h>
#include <openssl/lhash.h>
 
/* Encryption and decryption */
 
void
cipher(int what, uint8_t *dst, uint8_t *src, uint8_t key)
{
BF_KEY bk;
 
BF_set_key(&bk, 1, &key);
BF_ecb_encrypt(src, dst, &bk, what);
}
 
void
double_encrypt(uint8_t *dst, uint8_t *src, uint8_t key[2])
{
cipher(BF_ENCRYPT, dst, src, key[0]);
cipher(BF_ENCRYPT, dst, dst, key[1]);
}
 
 
/* Attacks */
 
const char report[] = "Key: \"%c%c\"\tOperations: %d\n";
const char notfound[] = "No keys founds in %d operations\n";
 
/*
* Bruteforce attack
*/
 
void
bruteforce(uint8_t *plaintext, uint8_t *ciphertext)
{
uint8_t buf1[8], buf2[8];
int i, j, op = 0;
 
for (i = 0; i < 256; i++) {
cipher(BF_DECRYPT, buf1, ciphertext, i);
for (j = 0; j < 256; j++) {
++op;
cipher(BF_DECRYPT, buf2, buf1, j);
if (memcmp(buf2, plaintext, 8) == 0) {
printf(report, j, i, op);
return;
}
}
}
printf(notfound, op);
}
 
/*
* Meet-in-the-middle attack
*/
 
/* Hash table of encrypted texts mapped to all possible keys */
typedef struct {
uint8_t enc[8]; /* encrypted text, hash table key */
uint8_t key; /* 8-bit encryption key */
} EK;
 
/* EK_hash works reliably only if long is 64 bits */
unsigned long EK_hash(const EK *v) { return *(unsigned long *)v->enc; }
static IMPLEMENT_LHASH_HASH_FN(EK_hash, const EK*);
 
int EK_cmp(const EK *v1, const EK *v2) { return memcmp(v1->enc, v2->enc, 8); }
static IMPLEMENT_LHASH_COMP_FN(EK_cmp, const EK*);
 
void
encrypt_all_keys(LHASH *h, EK items[], uint8_t *plaintext)
{
int i;
 
for (i = 0; i < 256; i++) {
items[i].key = i;
cipher(BF_ENCRYPT, items[i].enc, plaintext, i);
lh_insert(h, &items[i]);
}
}
 
void
meetinthemiddle(uint8_t *plaintext, uint8_t *ciphertext)
{
EK items[256], lookup, *found;
LHASH *h;
int i;
 
if ((h = lh_new(LHASH_HASH_FN(EK_hash),
LHASH_COMP_FN(EK_cmp))) == NULL) {
warn("hash table");
return;
}
encrypt_all_keys(h, items, plaintext);
 
for (i = 0; i < 256; i++) {
cipher(BF_DECRYPT, lookup.enc, ciphertext, i);
if ((found = lh_retrieve(h, &lookup)) != NULL) {
printf(report, found->key, i, i+256);
goto done;
}
}
printf(notfound, i+256);
done:
lh_free(h);
}
 
#define MEASURE(x) do { \
printf("%s\n", #x); \
clock_t t = clock(); (x); \
printf("%.3f sec\n\n", (clock()-t)/(double)CLOCKS_PER_SEC); \
} while (0)
 
int
main()
{
uint8_t plaintext[8] = "Dear Bob";
uint8_t key[2] = "Go";
uint8_t ciphertext[8];
double_encrypt(ciphertext, plaintext, key);
 
MEASURE( bruteforce(plaintext, ciphertext) );
MEASURE( meetinthemiddle(plaintext, ciphertext) );
 
return 0;
}

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.