On Sept 30, 2014 I sent two emails to Dr. Blum explaining what I believed was the weakness with the approach he was advocating. He never responded (or somehow I never saw a response).<p>Here is a snip from the first email:<p>Begin ---%<------------%<---------------------------------<p>As I understand it, the algorithm, expressed in Python is:<p><pre><code> #########################
import sys
from string import ascii_uppercase as alphabet
# ABCDEFGHIJKLMNOPQRSTUVWXYZ
LETTER = "31415926535897932384626433"
NUMBER = [0,2,4,6,8,1,3,5,7,9]
def f(ch):
assert ch in (alphabet + "0123456789")
if ch in alphabet:
return int(LETTER[alphabet.index(ch)])
if ch in "0123456789":
return int(ch)
def g(n):
return NUMBER[(NUMBER.index(n) + 1) % 10]
def pw(s):
digit = g((f(s[0]) + f(s[-1])) % 10)
result = [digit]
for c in s[1:]:
digit = g((digit + f(c)) % 10)
result.append(digit)
return result
print(sys.argv[1], pw(sys.argv[1]))
#########################
</code></pre>
Consider a few results from encryption and what it presents to the adversary:<p><pre><code> pw(“ABC”) == 928
pw(“ABCABC”) == 928362
</code></pre>
If “ABC” is a seed to the algorithm, then any seed that shares a prefix and a final character will have information leaked, sometimes enough to reveal the entire generated password for a different seed.<p>It’s actually worse than this. For example, if the adversary knows that:<p><pre><code> pw(“AAT”) == 941
pw(“ABC”) == 928
pw(“BBC”) == 717
</code></pre>
then the adversary knows that the mapping from the character C to an integer is the same as the mapping from character T. Using the terminology presented in the lecture this is<p><pre><code> f(“C”) == f(“T”)
</code></pre>
and from this adversary can determine information about the result of the password algorithm on other seeds.<p><pre><code> pw(“BBT”) == 717
pw(“B.*T”) == 7.*
</code></pre>
Because the algorithm uses a recurrence that generates one ciphertext character from the result of preceding ciphertext character, the adversary can make further inferences:<p><pre><code> pw(“BAT”) == 728
</code></pre>
which implies that if the preceding ciphertext is 7 and the current seed character is A that the resulting ciphertext will be 2. Consider<p><pre><code> pw(“BAT”) == 728
pw(“XAB”) == 725
pw(“XAAB”) == 7271
pw(“XAAAB”) == 72725
</code></pre>
End ---%<------------%<---------------------------------<p>My second email on Sept 30, 2014 contained the solution to a challenge he proposed in the video of a lecture on the method he gave:<p>Begin ---%<------------%<---------------------------------<p>On one slide during your recent lecture, you present a bit of a challenge, and I noticed that by making use of just the four plaintext/ciphertext pairs:<p><pre><code> BRAIN -> 06076
TRAIN -> 27732
GRAIN -> 35618
DRAIN -> 54349
</code></pre>
One can conclude that the permutation of [0,1,2,3,4,5,6,7,8,9] that controls the mapping g() must be one of the cycles:<p><pre><code> 6159073428
8106279354 <- this turns out to be the one
</code></pre>
In fact, with a bit more work one can deduce that it is the second by making use of the additional plaintext/ciphertext pair (which appears on the same slide):<p><pre><code> AND -> 496
</code></pre>
So now we know that<p><pre><code> g(0) -> 6
g(1) -> 0
g(2) -> 7
g(3) -> 5
g(4) -> 8
g(5) -> 0
g(6) -> 2
g(7) -> 9
g(8) -> 1
g(9) -> 3
</code></pre>
With g() in hand, it is short work to build up the mapping of f(). For these five words, the letters involved are A, B, D, G, I, N, R, and T.<p><pre><code> f(A) -> 5
f(B) -> 8
f(D) -> 0
f(G) -> 6
f(I) -> 2
f(N) -> 3
f(R) -> 0
f(T) -> 0
</code></pre>
Notes on decryption
===================<p>The details of this decryption aren't very interesting, so I won’t go into detail. I didn't need to use a computer, just paper and pencil. The important observation was that from BRAIN -> 06076 one knows<p>g(0 + f(R)) -> 6<p>and from TRAIN -> 27732 one knows<p>g(2 + f(R)) -> 7<p>thus if g(k) -> 6, g(k+2) -> 7.<p>This means that map(g, [0,1,2,3,4,5,6,7,8,9]) is some rotation of the list [_,_,_,_6,_,7,_,_,_,_] where 6 and 7 are at two locations apart.<p>Every letter, say 'A', which appears in more than two places in any of the plaintext/ciphertext pairs reveals information about g(). So BRAIN -> 06076
and TRAIN -> 27732 also reveals that<p>g(6 + f(A)) -> 0 and g(7 + f(A)) -> 7<p>Therefore, if g(k) -> 0 then g(k+1) -> 7. Thus, we can now conclude that map(g, [0,...,9]) is some rotation of [_,_,_,_,6,0,7,_,_,_].<p>In this fashion I concluded that map(g,[0,...,9]) was some rotation of
[2,9,1,3,6,0,7,5,8,4]. I knew that g()'s corresponding permutation was a circular permutation with a single cycle because that was a part of the system that makes it easier to memorize.<p>In general, of course, there could be ten possible mappings, one for each rotation. However, in practice some of these rotations
won't produce a permutation with a single cycle. This isn't really a problem because ten possible mappings for g() are still easy to validate in the next phase where we derive the mapping f(). In this particular case, there were only two possible circular permutations making it easy to decrypt the system with just paper and pencil.<p>The next step is to try out each of the possible g()'s determined above on the plaintext/ciphertext pairs. For example, BRAIN -> 06076 implies that<p>g(0 + f(R)) = 6<p>applying the inverse map of g() to both sides<p>0 + f(R) = 0<p>so<p>f(R) -> 0<p>In this manner the entire decryption can be performed.<p>End ---%<------------%<---------------------------------