Richard Heathfield
unread,Jun 8, 2017, 9:30:29 PM6/8/17You do not have permission to delete messages in this group
Sign in to report message
Either email addresses are anonymous for this group or you need the view member email addresses permission to view the original message
to
I had an idea for an attack on VeeCrypt that does not require any known
plaintext.
As is usual for me in such cases, I'm going to give you a blow-by-blow
account - this article is being composed iteratively: do some work,
write it down, do more work, write it down, etc.
Whether it's going to *work* is of course something that I don't know at
this stage, but by the time we get to the end of the article I'll know
one way or the other.
IF IT DOESN'T WORK, I will change the Subject line from:
"CT-ONLY ATTACK on VeeCrypt cryptosystem"
to:
"IDEA FOR CT-ONLY ATTACK on VeeCrypt cryptosystem"
:-)
Update: it works just fine, and I decided on "BREAK" rather than "ATTACK".
Partly to keep the length of this article within manageable bounds, and
partly out of sheer embarrassment, I won't be showing source code. If at
any point you want source code, say so and I'll think about posting it.
But I didn't get paid for writing this code, so it's likely to be quick
(to write), dirty (to look at), and crap (not very robust). On this
occasion, I don't care, because the proof of the pudding is in the
plaintext (if I can get at it).
Now, I should explain the context of the attack.
I challenged AOB to provide me with seven short ciphertexts (c. 60
characters, about ten English words), all encrypted with the same key
and using the same "variant" (whatever the hell that is).
He declined, because he knows VeeCrypt is not secure enough to withstand
such an attack.
Seven? Why seven? Well, it was a finger in the air. A guess. I don't
know how many ciphertexts this attack will need. If it works, though, it
shouldn't need many. My instinct is that seven will be plenty.
Of course, his refusal does mean I'm stuck for ciphertext. I have a copy
of VeeCrypt, but I have no idea how to change the key. So I'm going to
have to use the key that's already in there. AOB will therefore claim
that I'm cheating, but everybody else knows, I trust, that I'm not.
Also, I've had to choose my own plaintexts. I did this by picking seven
lines at random from an English text corpus. Have I seen those lines?
Yes. But that was, oh, about an hour ago [at the time of writing that
sentence: it's now three and a half hours ago], and I've already
forgotten them. (I do, however, know where they came from, and I'll do
my best to forget that knowledge.)
If this attack works out, I'm sure I'll be able to repeat it with other
ciphertexts supplied, perhaps, by willing collaborative Eves with their
own copies of VeeCrypt.
Finally: I'm going to stop, *not* when the job is done, but when it
becomes obvious that either (a) this is working, or (b) it isn't.
Even if it doesn't work out, I'm still going to post this article
because it may inspire someone else to come up with a modification that
might work better.
Now, the first job is pure housekeeping. I have to give you the
ciphertext, and AOB's formatting is just dreadful. So I wrote a program
to format the ciphertext into nice columns.
Here, then, are the ciphertexts:
ct01.txt:
-57 -29 -95 -89 -54 347 -93 -25 267 12 -82 -8
-64 -99 -88 -96 -58 -98 -86 -29 -78 -16 -89 -68
-94 -28 -96 -86 13 -109 -109 76 -102 -4 -39 -58
-91 -85 -90 126 -23 -53 -99 -101 -36 -76 152 -93
-29 -16 -102 -19 -40 -80 6 -106 -76 6 -82 -93
-27
ct02.txt:
-56 -98 -28 -90 -42 356 -100 -94 277 91 -77 -93
-75 -22 -93 -107 -64 -97 -17 -101 -86 -99 -12 -69
-101 -106 -85 -92 -56 -20 -95 161 -87 -83 -47 -82
-25 -91 -76 209 -107 -49 -89 -22 -37 -82 163 -87
-105 49 -58 -88 -50 -76 13 -102 -89 14 -95 -93
-27
ct03.txt:
-57 -113 -28 -97 -34 340 -25 -103 276 26 -80 -84
-80 -22 -93 -104 -70 -102 -17 -108 -20 -83 -88 -82
-83 -103 -17 -103 -59 -89 -108 161 -107 -73 33 -58
-109 -12 -82 144 -106 -61 -32 -22 -26 -73 146 -91
-111 49 -98 -84 -51 -90 10 -101 -78 82 -96 -93
-27
ct04.txt:
-60 -98 -111 -94 -51 358 -93 -94 345 15 -77 -87
-66 -91 -91 -25 -68 -104 -82 -111 -97 -92 -81 -71
-30 -28 -19 -57 13 -88 -109 161 -98 -83 -51 7
-106 -97 -79 125 -92 23 -90 -101 -37 -79 151 -109
-41 47 -18 -91 -37 -7 0 -88 -80 14 -26 -93
-27
ct05.txt:
-57 -29 -115 -75 -45 348 -94 -93 345 23 -77 -95
-69 -22 -107 -104 15 -104 -89 -98 -13 -99 -96 -68
-100 -101 -96 -94 13 -107 -103 77 -92 -4 -51 -65
-94 -89 -18 209 -88 -55 -88 -22 -45 -75 161 -100
-29 -38 -83 -97 -36 -76 1 -92 -75 82 -96 -93
-27
ct06.txt:
-67 -101 -97 -92 -45 344 -92 -100 345 51 -77 -84
-68 -91 -106 -25 -72 -85 -100 -29 -97 -98 -77 -81
-99 -98 -96 -98 -64 -89 -98 161 -107 -76 -36 -71
-25 -84 -75 209 -110 -42 -103 -22 -33 -82 146 -22
-114 -31 -97 -97 32 -90 -2 -90 -79 82 -77 -93
-27
ct07.txt:
-68 -101 -97 -10 -3 344 -108 -92 266 14 -64 -77
9 -70 -102 -104 -61 -32 -17 -116 -85 -89 -79 -75
-16 -101 -100 -16 -52 -20 -106 88 -104 -88 -43 -62
-25 -94 -75 140 -91 10 -91 -95 -43 -87 230 -105
-101 -20 -87 -103 32 -86 13 -23 -94 17 -96 -93
-27
Okay.
Now, I'm going to write my programs in such a way that I can choose how
much ciphertext to give them. This is an attempt to see just how much
ciphertext I actually *need*. I know I can't do it with one, but I don't
know whether or not I can do it with two. So I'll start with two, and
bring in new ciphertexts only when I have to.
This is an attack on the KEY, not the ciphertexts themselves. Once I
have the key (and I mean the real key, not the nonsensical obfuscated
version found in the source code), I can decipher /everything/ that is
encrypted with that same key and that same "variant" (whatever the hell
that is).
All right, so this key is *huge*, right? So brute force is not an
option. (It's never an attractive option anyway.)
But if we can /reduce/ the number of possible keys, a la Turing, we
might bring the problem into the realm of the achievable. That's the
plan, anyway.
(This is beginning to sound like one of those "engineering feats"
documentary scripts that draws you in with its purple prose but, at the
end, you realise that all you've learned in 45 minutes is "it's quite
big" or "it's quite fast and it cost a lot". Sorry about that.)
Okay, so let's really make a start. I feel a program coming on. Be right
back.
+++ OUT OF CHEESE ERROR - REDO FROM START +++
Done. Now, *what* have I done?
I've written a program that does this:
int f = 2;
while(f < argc)
{
int ct = ctfetch(argv[f], column);
ctfetch() opens the given file, keeps reading the ciphertext until it
hits the specified column, and returns the ciphertext in that column
(bear in mind that a column is several characters wide - we are fetching
the numerical equivalent of a string such as "-188" or whatever).
Now comes the logic. Given ct, we know that the key FOR THAT COLUMN must
be in the range ct+32 to ct+126. So we set the min and max accordingly.
BUT... the same rules apply for *every* ciphertext encrypted with the
same key. So let's see what happens when we give it just ONE ciphertext:
$ ./vckeyspace 0 ct01.txt
Range of keys for Column 0 is MIN -25, MAX 69 (inclusive)
That's the full 95-byte range. So, *OF COURSE*, we haven't achieved
anything. But then, we didn't expect to - not with /one/ ciphertext.
Let's try it with two:
$ ./vckeyspace 0 ct01.txt ct02.txt
Range of keys for Column 0 is MIN -24, MAX 69 (inclusive)
HA! I have now proved that this is going to do /some/ good. Right, let's
up it to three.
$ ./vckeyspace 0 ct01.txt ct02.txt ct03.txt
Range of keys for Column 0 is MIN -24, MAX 69 (inclusive)
Fat lot of good that did. But then we observe that ct01.txt and ct03.txt
start with the same ciphertext character, so perhaps it's not
surprising. Let's move on.
Adding ct04.txt changes the range to: -24 to 66
Adding ct05.txt doesn't change anything.
Adding ct06.txt changes the range to: -24 to 59
Adding ct07.txt changes the range to: -24 to 58
So we have eliminated twelve key candidates. That's stage 1. Now for
stage 2 of the attack. It's not pretty. It's brute force. But it's only
brute-forcing ONLY the keys that we know are candidates.
Let's try it.
$ ./vcattack 0 -24 58 ct01.txt
!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrs
Okay, that doesn't tell us much, does it? Let's try it with two files:
!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrs
!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqr
I don't think I'll bother with this incremental approach! Here are
*seven* files. Unfortunately, my newsreader is wrapping lines on me,
which makes the output a little messy at this stage. Hopefully things
will get tidier later on:
!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrs
!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqr
!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrs
$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuv
!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrs
+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}
,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~
In my shell, each output is on one line.
What am I looking for?
Well, what I want to see is a COLUMN in which EVERY character is plausible.
Here are the first couple of dozen columns:
!"#$%&'()*+,-./0123456789
!"#$%&'()*+,-./012345678
!"#$%&'()*+,-./0123456789
$%&'()*+,-./0123456789:;<
!"#$%&'()*+,-./0123456789
+,-./0123456789:;<=>?@ABC
,-./0123456789:;<=>?@ABCD
Now, I ask myself what the chances are that Alice would send seven
messages to Bob II, three of which begin with !
It's no more plausible than a plaintext of z&fre29\+
And I think the same applies to all of these columns. Let's count them: 25.
So I'm going to increase the minimum key by 25, which gives me this:
:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrs
9:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqr
:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrs
=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuv
:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrs
DEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}
EFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~
Ah! Much neater. But I think we can go further:
Column 0, keys 7 to 58:
@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrs
?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqr
@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrs
CDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuv
@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrs
JKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}
KLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~
It's early days, of course, but we've got the keyspace down from 95 to
52 for this column. We could eliminate quite a few more of these
columns, and maybe later we will, but the obvious ones to lose are in
the middle, and it's obviously easier to work with contiguous ranges for
as long as we can.
INTERIM RESULT FOR COLUMN 0: 7 TO 58
Now let's turn to column 1. First, let's minimax the keyspace:
$ ./vckeyspace 1 ct01.txt ct02.txt ct03.txt ct04.txt ct05.txt ct06.txt
ct07.txt
Range of keys for Column 1 is MIN 3, MAX 13 (inclusive)
WOW! We have only 11 possible keys for Column 1! Fantastic! Let's look
at them using vcattack:
!"#$%&'()*
efghijklmno
tuvwxyz{|}~
efghijklmno
!"#$%&'()*
hijklmnopqr
hijklmnopqr
RESULT! Look at the columns. In column 0 we have space (twice), e
(twice), t, and h (twice). In every other column we have unlikely stuff.
INTERIM RESULT FOR COLUMN 0: 7 TO 58
RESULT FOR COLUMN 1: Key is 3.
Right, now we need to match this up with Column 0:
@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrs
(row of spaces)
?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqr
eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee
@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrs
tttttttttttttttttttttttttttttttttttttttttttttttttttt
CDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuv
eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee
@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrs
(row of spaces)
JKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}
hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh
KLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~
hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh
Look at the last pair of lines. The first plausible result is "Ph". So
we can eliminate another 5 keys from column 0.
INTERIM RESULT FOR COLUMN 0: 12 TO 58
RESULT FOR COLUMN 1: Key is 3.
EFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrs
(row of spaces)
DEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqr
eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee
EFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrs
ttttttttttttttttttttttttttttttttttttttttttttttt
HIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuv
eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee
EFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrs
(row of spaces)
OPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}
hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh
PQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~
hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh
Now for column 2!
$ ./vckeyspace 2 ct01.txt ct02.txt ct03.txt ct04.txt ct05.txt ct06.txt
ct07.txt
Range of keys for Column 2 is MIN 4, MAX 11 (inclusive)
Just eight keys. What do they give us?
cdefghij
!"#$%&'
!"#$%&'
stuvwxyz
wxyz{|}~
efghijkl
efghijkl
Let's look at ct01:
EFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrs
(row of spaces)
What's the most plausible?
ccccccccccccccccccccccccccccccccccccccccccccccc
ddddddddddddddddddddddddddddddddddddddddddddddd
eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee
fffffffffffffffffffffffffffffffffffffffffffffff
ggggggggggggggggggggggggggggggggggggggggggggggg
hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj
Well, it's impossible to tell. Moving on to ct02:
DEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqr
eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee
What's the most plausible?
(row of spaces)
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
"""""""""""""""""""""""""""""""""""""""""""""""
###############################################
$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
'''''''''''''''''''''''''''''''''''''''''''''''
Frankly, I'm only tempted by the space and the apostrophe.
I don't think that moved us on very far, so let's try the next column.
$ ./vckeyspace 3 ct01.txt ct02.txt ct03.txt ct04.txt ct05.txt ct06.txt
ct07.txt
Range of keys for Column 3 is MIN 22, MAX 29 (inclusive)
Just 8 keys. You know what? I'm going to lose column 0! I'll represent
its value with a ?, and display column 1 as our key column instead. I'm
going to use _ to represent space.
?_[cdefghij]
?e[_!"#$%&']
?t[_!"#$%&']
?e[stuvwxyz]
?_[wxyz{|}~]
?h[efghijkl]
?h[efghijkl]
All right, what about column 3?
opqrstuv
pqrstuvw
wxyz{|}~
tuvwxyz{
abcdefgh
rstuvwxy
!"#$%&'
So now we have:
?_[cdefghij][opqrstuv]
?e[_!"#$%&'][pqrstuvw]
?t[_!"#$%&'][wxyz{|}~]
?e[stuvwxyz][tuvwxyz{]
?_[wxyz{|}~][abcdefgh]
?h[efghijkl][rstuvwxy]
?h[efghijkl][_!"#$%&']
I'm tempted by ?her and ?he_ for the last two.
Let's see what might fit:
Oher/Phe_
Pher/Qhe_
Qher/Rhe_
Rher/She_
Sher/The_
Ther/Uhe_
Uher/Vhe_
Vher/Whe_
Wher/Xhe_
Xher/Yhe_
Yher/Zhe_
Zher/[he_
(then we have [\]^_` which all seem unlikely as a first character apart
from the backtick, and lower case equivalents of the above.)
By far the most tempting is Sher/The_
I'm going to call that a result. If it's wrong, we can always come back
to it:
RESULT FOR COLUMN 0: Key is 16.
RESULT FOR COLUMN 1: Key is 3.
RESULT FOR COLUMN 2: Key is 4.
RESULT FOR COLUMN 3: Key is 22.
So we have:
I_co
He_p
It_w
Lest
I_wa
Sher
The_
This is working. Good. On to column 4.
$ ./vckeyspace 4 ct01.txt ct02.txt ct03.txt ct04.txt ct05.txt ct06.txt
ct07.txt
Range of keys for Column 4 is MIN 29, MAX 72 (inclusive)
HUGE range. I'm tempted to use a ? as a placeholder and move on. But we
have quite a bit of plaintext now, so why not see what will fit?
STUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~
GHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqr
?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghij
PQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{
JKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstu
JKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstu
!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJK
I_coS is silly, as is any capital in that position. So let's chop to the
'a', which loses 14 key candidates:
abcdefghijklmnopqrstuvwxyz{|}~
UVWXYZ[\]^_`abcdefghijklmnopqr
MNOPQRSTUVWXYZ[\]^_`abcdefghij
^_`abcdefghijklmnopqrstuvwxyz{
XYZ[\]^_`abcdefghijklmnopqrstu
XYZ[\]^_`abcdefghijklmnopqrstu
./0123456789:;<=>?@ABCDEFGHIJK
"Sher" can't realistically be followed by an upper case letter or any of
[\]^_` - and the only things that remain when we eliminate those are
lower case letters, which seems reasonable; and I don't believe {|}~
after "I_co", so we can lose another 13 candidates:
jklmnopqrstuvwxyz
^_`abcdefghijklmn
VWXYZ[\]^_`abcdef
ghijklmnopqrstuvw
abcdefghijklmnopq
abcdefghijklmnopq
789:;<=>?@ABCDEFG
The plaintext so far:
I_co
He_p
It_w
Lest
I_wa
Sher
The_
Now, "He_p^", "He_p_", and "He_p`" aren't promising, so we can lose
another three:
mnopqrstuvwxyz
abcdefghijklmn
YZ[\]^_`abcdef
jklmnopqrstuvw
defghijklmnopq
defghijklmnopq
:;<=>?@ABCDEFG
And now let's look at the last row. Do we really believe that "The_" can
be followed by any of that punctuation? Of course not. So we can lose
another seven key candidates:
tuvwxyz
hijklmn
`abcdef
qrstuvw
klmnopq
klmnopq
ABCDEFG
Much more manageable! All right, "It_w'" doesn't look right, so our
final paring is:
uvwxyz
ijklmn
abcdef
rstuvw
lmnopq
lmnopq
BCDEFG
Let's try the last column:
I_coz
He_pn
It_wf
Lestw
I_waq
Sherq
The_G
No. the one before:
I_coy
He_pm
No. The one before:
I_cox
He_pl
It_wd
No. So we have:
uvw
ijk
abc
rst
lmn
lmn
BCD
And neither "He_pj" nor "He_pk" is realistic, so that means we have our
key for column 4:
I_cou
He_pi
It_wa
Lestr
I_wal
Sherl
The_B
I'm a bit worried by "Lestr", but it can't be anything else, so let's
just trust it for now. If it becomes infeasible, we'll have to go back.
On to column 5! (By the way, these are 0-based, so column 5 is not the
fifth column, but the sixth.)
$ ./vckeyspace 5 ct01.txt ct02.txt ct03.txt ct04.txt ct05.txt ct06.txt
ct07.txt
Range of keys for Column 5 is MIN 390, MAX 466 (inclusive)
77 keys is too many, of course, but looking at the plaintext I want to
see no fewer than SIX lower case letters. The last row might be upper or
lower case, or it might be some other character. ("The B.B.C.", for
example.)
This requirement reduces this Column 5 mess:
+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvw
"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmn
23456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~
!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijkl
*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuv
./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz
./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz
to this:
lmnopqrs
cdefghij
stuvwxyz
abcdefgh
klmnopqr
opqrstuv
opqrstuv
Here's our plaintext:
I_cou
He_pi
It_wa
Lestr
I_wal
Sherl
The_B
I don't like 'z' on "It_wa", I don't like a second 'i' on "He_pi", and I
don't like 'q' on "I_cou". I don't like 's' on "The B" or 'r' on
"Sherl", let alone a 'q' or 'p', and that *only* leaves the first
column, Key 455.
I_coul
He_pic
It_was
Lestra
I_walk
Sherlo
The_Bo
On to column 6.
$ ./vckeyspace 6 ct01.txt ct02.txt ct03.txt ct04.txt ct05.txt ct06.txt
ct07.txt
Range of keys for Column 6 is MIN 7, MAX 18 (inclusive)
That doesn't look too bad. Let's look at them:
defghijklmno
klmnopqrstuv
!"#$%&'()*+
defghijklmno
efghijklmnop
cdefghijklmn
stuvwxyz{|}~
For "I_coul", the *only* possibility of those shown is 'd', which gives
us a key of 7 for column 6, and a plaintext collection that looks like this:
I_could
He_pick
It_was_
Lestrad
I_walke
Sherloc
The_Bos
One more. Column 7.
$ ./vckeyspace 7 ct01.txt ct02.txt ct03.txt ct04.txt ct05.txt ct06.txt
ct07.txt
Range of keys for Column 7 is MIN 7, MAX 23 (inclusive)
!"#$%&'()*+,-./0
efghijklmnopqrstu
nopqrstuvwxyz{|}~
efghijklmnopqrstu
defghijklmnopqrst
klmnopqrstuvwxyz{
cdefghijklmnopqrs
(It's interesting that the first *possible* key tends to *be* the key.)
Okay, by far the likeliest column is that first one, which gives us:
I_could_
He_picke
It_was_n
Lestrade
I_walked
Sherlock
The_Bosc
And it's obviously working. THAT is a CRACK. VeeCrypt just went down for
the third time, this time to a CIPHERTEXT-ONLY attack.
Result.
It took two and a half hours to crack this open to my own satisfaction
(including the time it took to write this article and the source code
that I used for minimaxing the keys and extracting candidate plaintext
characters). Retrieving the whole plaintext would take a fair bit
longer, but as you can see, the process accelerates all the time.
Austin: Big keyspaces do NOT imply infeasibly long decryption times.
WHEN will you learn this?
--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within