0: # Simple-xor encryption (which is very insecure) works like
1: # this:
2: #   $cipher[$i] = chr(ord($plain[$i]) ^ $key[$i%@key])
3: # Double-xor has an extra key, like this:
4: #   $cipher[$i] = chr(ord($plain[$i]) ^ $key1[$i%@key1]
5: #                     ^ $key2[$i%@key2])
6: # The claim has been made that double-xor encryption has an
7: # effective key length equal to the product of the lengths
8: # of the two keys, making it much more secure than
9: # simple-xor.  This is not true.  Below is a very
10: # efficient known plaintext attack that recovers the two
11: # xor keys, given a number of known bytes about equal to
12: # the sum (not the product) of the key lengths.  This is
13: # done using base-2 linear algebra -- I thought the matrix
14: # reduction step was kind of cool.  This attack is easily
15: # generalized to triple-xor or higher.
16: 
17: # Note: If you xor every element in the two keys by a
18: # constant value, the constant will cancel out when you do
19: # the encryption.  The keys determined by the method
20: # presented here might therefore be off by a constant, but
21: # it doesn't matter because they will encrypt and decrypt
22: # just the same.
23: 
24: # Getting the known plaintext is surprisingly easy.  The
25: # upper bits of ASCII text are very nonrandom (for
26: # instance, since lower case letters are most common, bits
27: # 5 and 6 are usually 1).  This makes it possible to work
28: # out the upper bits of the xor keys using other
29: # techniques.  Once that is done, you can guess which
30: # ciphertext characters correspond to spaces in the
31: # plaintext.  A little more guesswork is often needed -
32: # try common words that are the right length.  I've been
33: # able to successfully attack messages of length about 3
34: # times the total length of the keys.  A skilled
35: # cryptanalyst could probably break an even shorter
36: # message.
37: 
38: # Input:
39: #   $keylen1, $keylen2: Length of the two xor keys
40: #   $cipher: The enciphered message
41: #   %plain: Known (or guessed) plaintext bytes.  Hash keys
42: #           are the position in the message
43: 
44: # Build the coefficient matrix.  Since it's very sparse,
45: # the rows are stored as hashes rather than arrays
46: my $columns = $keylen1 + $keylen2;
47: my @matrix;
48: while (my ($pos, $ch) = each %plain) {
49:   my $i = $pos % $keylen1;
50:   my $j = $pos % $keylen2 + $keylen1;
51:   my $val = ord($ch) ^ ord(substr $cipher, $pos, 1);
52:   push @matrix, { $i=>1, $j=>1, val=>$val, "pos$pos"=>1 };
53: }
54: 
55: # Row-reduce the matrix
56: my $rank = 0;
57: foreach my $col (0..$columns-1) {
58:   # choose a pivot row which depends on $col
59:   my $i;
60:   for ($i = $rank; $i < $columns; $i++) {
61:     last if $matrix[$i]->{$col};
62:   }
63:   next if $i >= $columns;
64:   my $pivot = $matrix[$i];
65:   @matrix[$rank, $i] = @matrix[$i, $rank]
66:       unless $i == $rank;
67:   $rank++;
68:   # remove the dependence on $col from the other rows
69:   foreach my $row (@matrix) {
70:     next if $row == $pivot || !$row->{$col};
71:     $row->{$_} ^= $pivot->{$_} or delete $row->{$_}
72:         for keys %$pivot;
73:   }
74: }
75: 
76: # Interpret results
77: if ($rank < $columns-1) {
78:   # Matrix is underdetermined
79:   print "Not enough information - guess more plaintext\n";
80: }
81: foreach my $row (@matrix[$rank .. $columns-1]) {
82:   # The rows above $rank provide a check that the guessed
83:   # plaintext is consistent
84:   if ($row->{val}) {
85:     print "Inconsistent plaintext given\n";
86:     # Examining the "posN" entries would give information
87:     # about which guesses were wrong
88:     last;
89:   }
90: }
91: # Even if the matrix is underdetermined or inconsistent,
92: # decrypting with the inferred key values may help improve
93: # the guesses
94: my @key = (0) x $columns;
95: foreach my $row (@matrix[0 .. $rank-1]) {
96:   my $i;
97:   for ($i = 0; $i < $columns; $i++) {
98:     last if $row->{$i};
99:   }
100:   $key[$i] = $row->{val} || 0;
101: }
102: print "Key: @key\n";