Cryptography-Digest Digest #728, Volume #13 Wed, 21 Feb 01 06:13:00 EST
Contents:
Re: question1,2,2a,3,4,5,5a,5b,5c,6 ("Douglas A. Gwyn")
Re: The Key Vanishes: Scientist Outlines Unbreakable Code, Read it and ("Douglas A.
Gwyn")
Re: A seriously different cipher concept (long) ("Bryan Olson")
Re: Super strong crypto ("Douglas A. Gwyn")
Re: Could someone compile it for me? (pink aka Chr. Boesgaard)
Re: New unbreakable code from Rabin? ([EMAIL PROTECTED])
Re: New unbreakable code from Rabin? (Mok-Kong Shen)
Re: New unbreakable code from Rabin? ([EMAIL PROTECTED])
Re: New unbreakable code from Rabin? ([EMAIL PROTECTED])
Re: Key expansion. ("Joseph Ashwood")
Re: New unbreakable code from Rabin? (Mok-Kong Shen)
Re: Question about password hashing and hash chaining ("Joseph Ashwood")
Re: Question about RSA excryption... ("Joseph Ashwood")
Re: MQV implementation ("Alexander Schmitt")
Re: New unbreakable code from Rabin? (Nicholas Sheppard)
----------------------------------------------------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: question1,2,2a,3,4,5,5a,5b,5c,6
Date: Wed, 21 Feb 2001 08:34:51 GMT
I agree with what Paul Rubin wrote, and have some additional comments.
> > 2a.Where can you find material to work on?
In conjunction with your study of Military Cryptanalytics (the
Callimahos & Friedman set, which supersedes Friedman's Military
Cryptanalysis except for portions of parts III and IV for which
the Callimahos version is not publicly available), I recommend
tackling "the Zendian problem", presented in Part II Vol. 2.
This exercise was originally designed for a team effort by
students in NSA's advanced cryptanalysis class. It is sufficiently
hard that of the half dozen people I know who have tackled it,
including some of the most experienced "civilian" cryptanalysts,
none has completely recovered all the information possible, some of
it available through traffic analysis (alone or in conjunction with
the cryptanalysis). Fortunately some of the systems used by Zendia
are easier to crack than others. In principle, they can all be
cracked with pencil and paper, although for some of the more
difficult ones computer assistance is valuable, to build tables,
test coincidence at various offsets, etc. There is a separate
book available from Aegean Park Press that has an introductory
section on traffic analysis and a starting hint for the ZP, but
if you can make an entry without the hint then given that you
have the MilCryp book you don't really need the traffic analysis
one. There is also a Web site that gives (partial) solutions for
the ZP, but I warn you that looking there before you have made
considerable progress on your own would ruin the exercise for you.
While the systems involved in the ZP are of Korean War vintage,
solution will reinforce many of the things that MilCryp taught,
much of which is relevant even to cryptanalysis of modern-day
systems (although the character of the work has changed due to
the need to automate so much of it). It is also fun to work out
such things as codewords for digits using real-world knowledge of
the likely caliber of a howitzer round, etc.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: The Key Vanishes: Scientist Outlines Unbreakable Code, Read it and
Date: Wed, 21 Feb 2001 08:37:46 GMT
"." wrote:
> From the article at:
> http://www.nytimes.com/2001/02/20/science/20CODE.html?pagewanted=all
Why are you posting copyrighted material when we already had the
URL for it? Very uncool.
------------------------------
From: "nospam"@"nonsuch.org" ("Bryan Olson")
Subject: Re: A seriously different cipher concept (long)
Date: Wed, 21 Feb 2001 08:37:28 GMT
Paul Pires wrote:
>Before I go further, It looks like you got me.
Scott Fluhrer's attack is conclusive - good work Scott.
Nevertheless....
[...]
>This is clear. It is also seems that this could be made to apply for any
>known plaintext, not just the case of all zeros.
Well, that's what I worked on (for much longer than I
intended). I'll extend the attack to known, not chosen,
plaintext. I'll assume four blocks of random plaintext and
the corresponding ciphertext. As in Fluhrer's explanation,
I'll use a random permutation to update A. Pires'
presentation is usually clear, but his permutation is
specified in "C" code that has implementation defined
behavior.
To show in detail how it works, I'm including working Python
code that recovers the vast majority of the initial A and B
tables, with good - but not perfect - accuracy. Python is
free and cleanly installable versions are available for most
of the popular platforms. If you've never used it, odds are
that you could in within a few minutes. See www.python.org.
In one block, we have a plaintext of 64 words, and a ciphertext
of 64 words. Each ciphertext word is one of the plaintext words
XOR one of the words in the B array. We can therefore generate
all 64*64 = 4096 words P[i] ^ C[j], 0 <= i, j < 64. The 64
elements of the B array must be among these 4096 candidates.
Say we start with plaintext[0] and state[0]. From these we
compute ciphertext[0] and update the state to state[1].
Then plaintext[1] and state[1] give use ciphertext[1] and
state[2] and so on. From plaintext[i] and ciphertext[i], we
can compute the 4096 candidates for the B values in
state[i]. We generate the 4096 candidates for each of our
four blocks of plaintext/ciphertext.
Given the candidate B values for state[i+1], along with
plaintext[i] and ciphertext[i], we can winnow down the
candidates B values for state[i], using:
If
x is in the B array of state[i], and
y is in the B array of state[i+1],
then,
there must be words
u in plaintext[i] and
v in ciphertext[i]
such that:
(x >> 5) == low_27_bits(y ^ u ^ v)
The variables x and y each range over 4096 == 2**12 values
and u and v each range over 64 == 2^6 values. About one is
2**27 value sets will satisfy the "such that" by chance.
The 64 correct B values will also pass (well, there's one
exception), so we get about 2**36 / 2**27 + 63 == 575
candidates.
We use the 4096 candidates for state[3] to reduce our
state[2] candidates to about 575. We then use the 575
state[2] candidates to reduce the state[1] number to about
135 candidates, and these to find about 80 candidate B
values for the initial state. The procedure bottoms out
between 70 and 80 candidates.
With this few candidates, we can look at cases where the
encryption function and state update function give us a
unique solution for the words of the plaintext and
ciphertext, and the B values. The state update function
adds C[i] to B[i], so if we find a unique solution it gives
us the location of the B value. Once we have locations for
the B values, we can find values in the A array.
Below is Python code demonstrating the attack. It usually
leaves about half a dozen members of the 64 initial A and B
arrays unknown, and on rare occasions gets a couple values
wrong. The errors and omissions could be corrected with
hand inspection or more complex code.
--Bryan
############# Begin Python code
from random import randrange
def permute(array):
"""Return a random permutation of the elements of the array.
"""
perm = array[:]
for i in range(len(perm)):
pos = randrange(i + 1)
(perm[i], perm[pos]) = (perm[pos], perm[i])
return perm
def rand32(dummy = None):
"""Return a random long integer in [0..2**32)
"""
return (long(randrange(0xFFFFFF)) << 16) | randrange(0xFFFFFF)
def random_block(dummy = None):
"""Return an array of 64 random 32-bit longs.
"""
return map(rand32, range(64))
#####################################################
class State:
"""Class for the state of Pires' cipher. Self intitializes randomly.
"""
def __init__(self):
self.A = permute(range(64))
self.B = map(lambda x: rand32(), [None] * 64)
self.x = 0
def encrypt(P, state):
"""Pires' encryption procedure, but generalized update of A.
"""
A = state.A
B = state.B
C = [None] * 64
# Encrypt
for i in range(64):
C[A[(i + 32) % 64]] = B[i] ^ P[A[i]]
# Update the State B table
roller = state.x ^ ((B[0] << 27) & 0xFFFFFFFFL)
for i in range(63):
B[i] = ((B[i] >> 5) ^ P[A[63 - i]] ^ C[i] ^
((B[i + 1] << 27) & 0xFFFFFFFFL))
B[63] = (B[63] >> 5) ^ P[A[0]] ^ C[63] ^ roller
# Just use a random permutation on A
state.A = permute(A)
state.B = B
state.x = state.x + 1
return C
##################################################
def get_4096(P, C):
"""Given a plaintext and ciphertext block, return the 2^12
candidates that could be values in the starting B array.
"""
result = []
for i in range(len(P)):
for j in range(len(C)):
result.append(P[i] ^ C[j])
return result
def cull(s1, s2, p, c):
"""Given possible values from the B array before and after
encrypting a block (found by get_4096 above), return a reduced
list of the possible starting B elements.
It uses a meet-in-the-middle tactic; it creates a table of size
len(s1) * len(p) and then does len(s2) * len(c) lookups.
"""
targets = {}
for w in s2:
for x in p:
targets[(w ^ x) & 0x07FFFFFF] = 1
cull_set = []
for w in s1:
for x in c:
if targets.has_key(((w >> 5) ^ x) & 0x07FFFFFF):
cull_set.append(w)
return cull_set
def find_B(s1, s2, p, c):
"""Given possible before and after B array values (as reduced
by cull above), and plaintext and ciphertext, return a B table
with some values filled in.
"""
targets = {}
for x in s1:
for y in s2:
targets[((x >> 5) ^ y) & 0x07FFFFFF] = x
B = [None] * 64
for j in range(len(c)):
y = c[j]
count = 0
index = None
value = None
for x in p:
targ = (x ^ y) & 0x07FFFFFF
if targets.has_key(targ):
index = j
value = targets[targ]
count = count + 1
if count == 1:
B[index] = value
return B
def find_A(B, p, c):
"""Given a partial B array, the plaintext and ciphertext,
return an A table with some values filled in. As a side effect,
possibly fill in a few more B values.
"""
B_inverse = {}
for i in range(len(B)):
B_inverse[B[i]] = i
A = [None] * 64
for u in range(len(p)):
x = p[u]
for v in range(len(c)):
y = c[v]
if B_inverse.has_key(x ^ y):
i = B_inverse[x ^ y]
A[i] = u
A[(i + 32) % 64] = v
for i in range(64):
if B[i] == None and A[i] != None and A[(i + 32) % 64] != None:
B[i] = p[A[i]] ^ c[A[(i + 32) % 64]]
return A
# Create an instance of the state, and save the intial
# values so we can check if we get them right.
s = State()
initial_A = s.A[:]
initial_B = s.B[:]
# Amount of known plaintext to assume
num_blocks = 4
# Create a random plaintext
plaintext = map(random_block, range(num_blocks))
# An encrypt into ciphertext
ciphertext = []
for a in range(num_blocks):
ciphertext.append(encrypt(plaintext[a], s))
# For each block, find 4096 candidate B elements
possible = [None] * num_blocks
for a in range(num_blocks):
possible[a] = get_4096(plaintext[a], ciphertext[a])
# Step backwards over the blocks, using the candidates of
# later states to reduce the number of candidates for the
# earlier states.
for a in range(num_blocks - 1, 0, -1):
possible[a-1] = cull(possible[a - 1],
possible[a],
plaintext[a-1],
ciphertext[a-1])
print "For state", a-1, "we have", len(possible[a-1]), "values"
# Solve for (most of) A and B
partial_B = find_B(possible[0], possible[1], plaintext[0], ciphertext[0])
partial_A = find_A(partial_B, plaintext[0], ciphertext[0])
# Print the results:
print "Array A, actual and computed:"
for i in range(64):
print i, initial_A[i], partial_A[i]
if partial_A[i] != None and initial_A[i] != partial_A[i]:
print "**** Mistake"
print "\nArray B, actual and computed:"
for i in range(64):
print i, initial_B[i], partial_B[i]
if partial_B[i] != None and initial_B[i] != partial_B[i]:
print "**** Mistake"
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Super strong crypto
Date: Wed, 21 Feb 2001 08:39:36 GMT
Bryan Olson wrote:
> The key changes in real systems are there to limit the damage
> from exposed keys; ...
No.
------------------------------
From: [EMAIL PROTECTED] (pink aka Chr. Boesgaard)
Subject: Re: Could someone compile it for me?
Date: 21 Feb 2001 10:11:09 +0100
"Ryan M. McConahy" <[EMAIL PROTECTED]> writes:
> Pllllllleeeeeeeeeeeeeeeeeeeeeeaseee???
Roll it yourself with djgpp:
http://www.delorie.com/djgpp/
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: New unbreakable code from Rabin?
Date: 21 Feb 2001 05:21:01 -0500
John Savard <[EMAIL PROTECTED]> wrote:
> Obviously, any random bit stream two participants are capable of
> exchanging is capable of being stored by an adversary.
The point is that this isn't such a bit stream.
No one generates, transmits or exchanges this bit stream.
They only exchange information on how to extract a bit
stream from a transient, public pool of random data.
The pool consists of ALL publicly accessible random,
but transient, data (that can be munged into a fully
entropic, n bits of entropy for n bits of length).
Black body (universal background) radiation from any
location at any time. Minute by minute stock fluctuations.
The density of the cloud cover on Jupiter. Possibly a service
that provides such a stream (from a satellite, I saw mentioned
in the article ... but I would not trust such a service provider
who could use a pseudo-random generator and so he would be
able to reconstruct any portion of the data stream at any
later time - it would not be "auto-erasing," transient, but
knowledge of the generator for the pseudo-random number
generator would enable one to "unerase" it).
Just SOME collection of publicly accessible random data that
is too voluminous for more than an infinitesimal portion to
be stored for more than a week, say.
It is a matter then of key sharing protocol. One does NOT
need to generate or share a long key. One can use fairly
weak encryption just to indicate what portion of the
random, transient, public pool to use as a key.
All one requires is that the weak encryption used to indicate
how to extract a key from the public pool, be strong enough
to resist an interceptor's efforts at decryption for a week
(long enough until the pool has "auto-erased").
It's a key generating protocol (not really an encryption method)
using a transient (due to volume, only a small bit can be stored)
public pool to enable one to obtain, say, theoretically unbreakable
(LONG, one time pad) keys from the pool by indicating how to extract
it using much weaker, shorter, simpler encryption. It avoids the
problems of needing absolute security in transmitting keys for
a one time pad by using a transient public source.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: New unbreakable code from Rabin?
Date: Wed, 21 Feb 2001 11:25:57 +0100
"Douglas A. Gwyn" wrote:
>
> Mok-Kong Shen wrote:
> > So one has a huge public (truly) random bit sequence
> > and it is the starting point of the segment which is
> > used to encrypt ...
>
> No, the key bits would not be contiguous. Their locations
> would be determined by a mutually-keyed index generator.
Thanks. I have two more questions: (1) Is it the secret key
of the index generator that prevents an eavesdropper from
getting the key stream? But then in an 'absolute' (maybe
pedantic) sense the security of that generator would have
to be considered. (2) Is a paper giving some technical
details available?
M. K. Shen
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: New unbreakable code from Rabin?
Date: 21 Feb 2001 05:28:10 -0500
Malcolm Herring <[EMAIL PROTECTED]> wrote:
> The critical point in this discussion has been missed. Even if this method
> of encryption is infinitely strong, it is compromised by "... communicating
> parties select a running sample from the bit stream pool according to some
> agreed-upon rule" - i.e. a key exchange. It is therefore only as strong as
> the key exchange system.
Yes. If the transient, public pool from which the data is extracted is
so voluminous that only an infinitesimal portion can be saved beyond the
last week's data, then one can have the full security of a fully random
key (extracted by both parties from that public pool using a method
shared by both parties indicated in a message sent with weaker encryption)
only if that weaker encryption can resist all attempts to crack it for
a week (by the time it is cracked, the information on how to extract
data from the public pool is useless since the public pool is transient
and too large for more than a week's data to be stored).
How weak can the method used to exchange the method for extracting a key
from the transient, public pool be?
That depends on how much of the transient data can be stored (if a week's
worth, then the encryption used to share the method *must* withstand
any attempts to crack it for at least a week).
So ... depending on the size of the pool and the amount of storage available
one can boost an encryption method that only is secure for a week, say,
to a method for securely choosing a large, random key (say, for a one-time-pad
with its absolute security).
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: New unbreakable code from Rabin?
Date: 21 Feb 2001 05:38:49 -0500
Hard <[EMAIL PROTECTED]> wrote:
> If we all have access to the same "random" bit stream, and I know that
> Dr. Invincible is going to send a short encrypted message to Mr. X at
> 16:00:00 hours today, what is to keep me from capturing 15:59:59 to
> 16:00:01 of that stream and just crunching the numbers on it? It
> seems trivial. Maybe I'm missing something.
How did you "know" that the message was going to be sent using data
from that stream of all the pulic random data at that time?
The idea is that the information as to what portion of some public
pool of data is to be used for the key (they may have extracted
data from the pool last week to generate keys to be used today) IS
encrypted as well (in this case, the portion of the pool of
random data that is used for the actual key for encryption) BUT
that this information can be sent using much weaker encryption so that
by the time you manage to crack it (and find out that they are sending
a message near 16:00 today) a week has passed (and it is too late) -
storing a week's worth of data is too much (as an example).
(of course there are details to handle ... traffic analysis ... if you
can predict when they share a message and they always extract AT THAT
TIME, instead of at some other random time, the random data from a
certain public data stream, then you can predict what portion of the
stream to store and you don't have to store so much as to make it
impossible for you to store enough to crack the message)
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Key expansion.
Date: Tue, 20 Feb 2001 14:29:07 -0800
"Cristiano" <[EMAIL PROTECTED]> wrote in message
news:96uk1l$c4e$[EMAIL PROTECTED]...
> "Ichinin" ha scritto:
> > Cristiano wrote:
> > > If I want to use 192 or 256 bits how would I do?
> > >
> > > There are problems if I withdraw only 128 bits instead of 160 (I don't
> want
> > > to use MD5)?
No problem. If you want fewer bits from a cryptographic hash function just
chop off the last bits. Now since you obviously have a variety of key sizes
in question (which by the way if you are using a short passphrase, the
security is only as good as that passphrase so 256-bit Rijndael will
probably be overkill, with that said):
128-bits: SHA-1 (chop off the last bits)
160-bits: SHA-1
192 : Tiger-192, or SHA-256 with the last bits chopped off
256 : SHA-256
384 : SHA-384
512 : SHA-512
and I'm sure if you need it we can find something larger than that
Joe
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: New unbreakable code from Rabin?
Date: Wed, 21 Feb 2001 11:44:00 +0100
[EMAIL PROTECTED] wrote:
>
[snip]
> Black body (universal background) radiation from any
> location at any time. Minute by minute stock fluctuations.
> The density of the cloud cover on Jupiter. Possibly a service
> that provides such a stream (from a satellite, I saw mentioned
> in the article ... but I would not trust such a service provider
> who could use a pseudo-random generator and so he would be
> able to reconstruct any portion of the data stream at any
> later time - it would not be "auto-erasing," transient, but
> knowledge of the generator for the pseudo-random number
> generator would enable one to "unerase" it).
You seem to point to a problem. If there is no central
service, how could it be ensured that everyone access the
same stream and not eventually manipulated (and also
differing) copies? If there is a central service, the
issue of trust arises.
>
> Just SOME collection of publicly accessible random data that
> is too voluminous for more than an infinitesimal portion to
> be stored for more than a week, say.
>
> It is a matter then of key sharing protocol. One does NOT
> need to generate or share a long key. One can use fairly
> weak encryption just to indicate what portion of the
> random, transient, public pool to use as a key.
>
> All one requires is that the weak encryption used to indicate
> how to extract a key from the public pool, be strong enough
> to resist an interceptor's efforts at decryption for a week
> (long enough until the pool has "auto-erased").
Couldn't an eavesdropper monitor the communications and
record simultaneously (during the time the communication
partners negotiate) the bits in the public pool for
later use?
Thanks.
M. K. Shen
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Question about password hashing and hash chaining
Date: Tue, 20 Feb 2001 15:56:38 -0800
<[EMAIL PROTECTED]> wrote in message news:96rgpf$gn6$[EMAIL PROTECTED]...
> (1) What is the correct way to get from the user-entered passphrase (a) to
> the
> input that a symmetric crypto algorithm like Blowfish expects (b)? Is it
> enough to just hash (a) with SHA1 for example?
Unless the symmetric algorithm expects specific formatting yes the correct
way is to just push it through SHA-1. I am not aware of any currently used
algorithms that expect special format for the key so you don't have to
worry.
>
> (2) Which one, in your opinion, is more secure: SHA1 or MD5?
SHA-1, beyond question. SHA-1 has a larger hash, and MD5 has a minor
weakness that is known.
>
> (3) When the crypto algorithm needs more input than the hash function
> supplies, which is the correct way to chain hash results? Should I re-hash
> part of the first result or the whole result? Should I append to the left
or
> to the right?
There is a lot of debate on this. The best general advice I can give is use
a bigger hash, there's also SHA-256, SHA-384, and SHA-512. You could also
perform various gyrations using hashs but I wouldn't recommend it.
>
> (4) I've once read (can't remember where) that cipher chaining does not
> provide significantly more security. This doesn't seem very logical to me:
> Suppose there's a specific unknown attack or weakness of algorithm A
> *exclusive-or* B, then I can minimize the risk by cipher-chaining A and B,
> can't I? Is there any reason why I shouldn't cipher-chain as many
algorithms
> as the speed of my implementation allows?
Another big debate. We do know that if the ciphers are completely
independent, and have unrelated keys, then the strength does not diminish.
All other quantities are strictly dependent on the ciphers in question.
>
> (5) As a test for the correct passphrase, would this suffice: Create a
hash
> of
> the ciphertext, encrypt the hash and store it. To test, create the hash of
> the ciphertext, decrypt the stored hash and compare the results...?
Yes that is sufficient to verify that he correct passphrase has been
entered. However to make it harder to perform dictionary attacks you should
add a salt in there somewhere, so you compute has(salt, passphrase) and
verify.
Joe
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Question about RSA excryption...
Date: Tue, 20 Feb 2001 16:24:13 -0800
Since others have addressed the whys, I'll address the how to fix.
The method to fix depends greatly on how much data you plan to encrypt. Both
assume you have possession of a cryptographically strong hash function, take
a look at SHA-1, SHA-256, SHA-284, and SHA-512 for a good selection of
sizes.
(given that the modulus has size n and the hash output has size k)
If your message is smaller than the size of the hash do the following:
pick a random number R that is n-k-1 bits in length
generate S = hash(R)
M = R | (S XOR message) (| is concatenation)
encrypt M
The second method is for messages larger than the size of your hash, and
requires an agreed upon cipher that takes a key with a size no larger than k
(the size of the hash)
choose a random Key of the correct size for the block cipher (which also
happens to be no larger than your hash function)
RSA_Encrypt(Key) //this will encrypt using the method above
BLOCK_Encrypt(Message, Key)
These avoid many of the pitfalls of RSA encryption
Joe
------------------------------
From: "Alexander Schmitt" <[EMAIL PROTECTED]>
Subject: Re: MQV implementation
Date: Wed, 21 Feb 2001 11:49:06 +0100
It hangs in the following part of the opt_inv routine of the fast inversion.
At the end of the process all elements of g = 0 and so the last element is
also g.e[LONGWORD] = 0, so that the task never will go out of the loop. So
it seems that not the signed or unsigned bit is responsible for the infinite
loop but the last bit is it.
Any hints?
do {
i = shift_by[g.e[LONGWORD] & 0xff];
n+=i;
/* Shift b left i (multiply by u^i), lengthening it if needed */
m = 0;
for ( j=LONGWORD; j>=c_top; j-- ) {
bits = b.e[j];
b.e[j] = (bits<<i) | m;
m = bits >> (WORDSIZE-i);
}
if ( m ) b.e[c_top=j] = m;
/* Shift g right i (divide by u^i) */
m = 0;
for ( j=f_top; j<=LONGWORD; j++ ) {
bits = g.e[j];
g.e[j] = (bits>>i) | ((ELEMENT)m << (WORDSIZE-i));
m = bits;
}
} while ( i == 8 && (g.e[LONGWORD] & 1) == 0 );
Alex
------------------------------
Date: Wed, 21 Feb 2001 12:18:07 +1100
From: Nicholas Sheppard <[EMAIL PROTECTED]>
Subject: Re: New unbreakable code from Rabin?
On 20 Feb 2001, Kenneth Almquist wrote:
> The New York Times asserts that this scheme is practical. I don't
> think it is. For example, assume that Alice and Bob communicate over
> a T1 link (1.5 Mbits/second), and the attacker has invested in an
> 80 gigabyte hard disk. To prevent the attacker from storing more
> than 1% of the random bit stream, the stream would have to be
> 703,687,441,776,640 bits long, which by my calculation would take
> nearly 15 years to transmit.
I'm not too sure on what the state-of-the-art transmission technology can
do these days, but if we all had "10 million million numbers" (bits?) per
second downlinks to our computers, I'm sure most of us could think of
plenty of things more interesting than random numbers to download.
Uncompressed 24-bit colour 1024x768 video at 30 frames per second requires
a mere 566 million bits per second, and I've never heard of a system that
can do that. The artice casually suggests we have a system with about
20000 times that bandwidth.
The practical security of the system seems to depend on the amount of data
a computer can store vs the amount of data it can generate. If the latter
is sufficiently fast compared to the former, the system will be secure in
a practical sense -- i.e. not "unbreakable", merely "infeasible", much the
same as any other cryptographic system.
--
Nicholas Sheppard | Ph: +61 2 4221 5290
Research Fellow | Fax: +61 2 4221 4170
School of Information Technology & Computer Science | E-mail: [EMAIL PROTECTED]
The University of Wollongong, Australia | WWW: www.uow.edu.au/~nps
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
