Cryptography-Digest Digest #732, Volume #13 Thu, 22 Feb 01 03:13:01 EST
Contents:
Re: The Key Vanishes: Scientist Outlines Unbreakable Code, Read it and (John Savard)
Re: ___indeed 2x2 Matrix RSA (kctang)
Re: The Key Vanishes: Scientist Outlines Unbreakable Code, Read it and (Hard)
Re: A different concept for email encryption ?? (Paul Crowley)
Re: Key expansion. (Paul Crowley)
What does tempest stand for. (Mark Healey)
super-stong crypto, straw man phase 2 ("Douglas A. Gwyn")
Re: Hardware RNG - Where can I order one? (Robert Davies)
Re: Is there an algorithm to sequentially enumerate all transcendental (Vaughan
Pratt)
Re: What does tempest stand for. (Hard)
Re: Fractal encryption? ("John A. Malley")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: The Key Vanishes: Scientist Outlines Unbreakable Code, Read it and
Date: Thu, 22 Feb 2001 04:27:58 GMT
On Wed, 21 Feb 2001 18:35:07 -0700, Sundial Services
<[EMAIL PROTECTED]> wrote, in part:
>I'm rather puzzled by the hooplah on this (although it's a great piece
>of journalistic copy). It's basically a one-time-pad encipherment that
>assumes that the two parties can simultaneously receive the same key
>stream, i.e. from an orbiting sattelite. Certainly this type of a
>system is provably and obviously secure ... IF the sun doesn't throw any
>sunspots at exactly the wrong time, Murphy's Law does not happen and so
>on. In fact I would be very surprised if it is not already in-use
>somewhere.
No, it's not a one-time-pad, because any eavesdropper can also tune in
to the orbiting satellite.
This is still secure, based on the assumption that the _total_ number
of random bits sent out by the satellite - which an eavesdropper would
need to use for trials in cryptanalyzing a message - is so big that
the eavesdropper could not store them all, but the parties could store
the small subset of those bits actually used in sending a message.
If you believe the assumptions, the theory is sound. But the
assumptions lead to a difference in difficulty for the parties and the
eavesdropper that is actually quite low when compared, say, to most
public-key cryptosystems. Because the mathematical proof doesn't
include a proof of how good a tape recorder can be.
Obviously, any single signal with bandwidth that can be handled by
digital circuitry can be recorded on a souped-up videotape recorder,
so we're talking about something fairly exotic; say an optical signal
with thousands of different wavelengths of light each modulated by a
complex signal involving hundreds of individual digital channels, each
on their own subcarrier. Now: is it possible to record, say, a million
simultaneous T1 connections?
*Unbreakable?* Maybe by Joe Hacker. But the technology to break this
is _precisely_ what the NSA is quite good at, because they've needed
special tape recorders to record - at once - all the radio signals in
a large chunk of the radio spectrum for ages.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: kctang <[EMAIL PROTECTED]>
Subject: Re: ___indeed 2x2 Matrix RSA
Date: Thu, 22 Feb 2001 13:19:09 +0800
==============CCCFA250B5D9E21B4DD8F3F7
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Jakob Jonsson wrote:
> > kctang wrote:
> > 1) Can you explain why this method works? (Anyhow, I shall
> > provide an example tomorrow.)
>
> Since the square of M is equal to diag(a^2+bc, a^2+bc), the procedure will
> work as soon as ed-1 is a multiple of 2*lcm(p-1, q-1) (e.g., (p-1)(q-1)) and
> a^2+bc != 0 mod n.
>
> > 2) Please provide a convincing crack, not just simply mention its
> > weakness.
>
> This is not a crack, but an observation:
>
> M^e = [e = 2k+1] = M^2k * M = (a^2+bc)^k * M
>
> Hence b*a^{-1} mod n, c*a^{-1} mod n, and b*c^{-1} mod n are easy to extract
> from M^e. This means that knowing one of the values a, b, c is enough to
> break the scheme. On the other hand, if b and c are completely random and
> independent, the task will be to determine a from a^e, b/a, and c/a, which
> is no easier than determining a from a^e, i.e., computing eth roots modulo
> n.
So there is no CONVINCING crack at this moment?
> In either case, nothing is gained compared to ordinary RSA.
But can I say?
"Since encryption/decryption can be carried out in 3 components for
each single run,
----> it is *3 minus something* times faster than RSA,
after taking into consideration of the overhead in computing MATRIX
exponentiation mod n."
Moreover, the scheme might be possible in generalizing to higher
dimension. So n times faster, for large n!
Any comments?
Thanks, kctang
==============CCCFA250B5D9E21B4DD8F3F7
Content-Type: text/html; charset=us-ascii
Content-Transfer-Encoding: 7bit
<!doctype html public "-//w3c//dtd html 4.0 transitional//en">
<html>
Jakob Jonsson wrote:
<blockquote TYPE=CITE>> kctang wrote:
<br>> 1) Can you explain why this method works? (Anyhow, I shall
<br>> provide an example tomorrow.)
<p>Since the square of M is equal to diag(a^2+bc, a^2+bc), the procedure
will
<br>work as soon as ed-1 is a multiple of 2*lcm(p-1, q-1) (e.g., (p-1)(q-1))
and
<br>a^2+bc != 0 mod n.
<p>> 2) Please provide a convincing crack, not just simply mention its
<br>> weakness.
<p>This is not a crack, but an observation:
<p>M^e = [e = 2k+1] = M^2k * M = (a^2+bc)^k * M
<p>Hence b*a^{-1} mod n, c*a^{-1} mod n, and b*c^{-1} mod n are easy to
extract
<br>from M^e. This means that knowing one of the values a, b, c is enough
to
<br>break the scheme. On the other hand, if b and c are completely random
and
<br>independent, the task will be to determine a from a^e, b/a, and c/a,
which
<br>is no easier than determining a from a^e, i.e., computing eth roots
modulo
<br>n.</blockquote>
<tt>So there is no CONVINCING crack at this moment?</tt>
<blockquote TYPE=CITE>In either case, nothing is gained compared to ordinary
RSA.</blockquote>
<tt>But can I say?</tt><tt></tt>
<p><tt>"Since encryption/decryption can be carried out in 3 components
for</tt>
<br><tt>each single run,</tt><tt></tt>
<p><tt>----> it is *3 minus something* times faster than RSA,</tt><tt></tt>
<p><tt>after taking into consideration of the overhead in computing MATRIX</tt>
<br><tt>exponentiation mod n."</tt><tt></tt>
<p><tt>Moreover, the scheme might be possible in generalizing to higher</tt>
<br><tt>dimension. So n times faster, for large n!</tt><tt></tt>
<p><tt>Any comments?</tt><tt></tt>
<p><tt>Thanks, kctang</tt>
<br><tt></tt>
<br><tt></tt>
<br> </html>
==============CCCFA250B5D9E21B4DD8F3F7==
------------------------------
From: [EMAIL PROTECTED] (Hard)
Subject: Re: The Key Vanishes: Scientist Outlines Unbreakable Code, Read it and
Date: Thu, 22 Feb 2001 06:30:52 GMT
On Thu, 22 Feb 2001 04:27:58 GMT, [EMAIL PROTECTED]
(John Savard) wrote:
>On Wed, 21 Feb 2001 18:35:07 -0700, Sundial Services
><[EMAIL PROTECTED]> wrote, in part:
>
>>I'm rather puzzled by the hooplah on this (although it's a great piece
>>of journalistic copy). It's basically a one-time-pad encipherment that
>>assumes that the two parties can simultaneously receive the same key
>>stream, i.e. from an orbiting sattelite. Certainly this type of a
>>system is provably and obviously secure ... IF the sun doesn't throw any
>>sunspots at exactly the wrong time, Murphy's Law does not happen and so
>>on. In fact I would be very surprised if it is not already in-use
>>somewhere.
>
>No, it's not a one-time-pad, because any eavesdropper can also tune in
>to the orbiting satellite.
>
>This is still secure, based on the assumption that the _total_ number
>of random bits sent out by the satellite - which an eavesdropper would
>need to use for trials in cryptanalyzing a message - is so big that
>the eavesdropper could not store them all, but the parties could store
>the small subset of those bits actually used in sending a message.
>
>If you believe the assumptions, the theory is sound. But the
>assumptions lead to a difference in difficulty for the parties and the
>eavesdropper that is actually quite low when compared, say, to most
>public-key cryptosystems. Because the mathematical proof doesn't
>include a proof of how good a tape recorder can be.
>
>Obviously, any single signal with bandwidth that can be handled by
>digital circuitry can be recorded on a souped-up videotape recorder,
>so we're talking about something fairly exotic; say an optical signal
>with thousands of different wavelengths of light each modulated by a
>complex signal involving hundreds of individual digital channels, each
>on their own subcarrier. Now: is it possible to record, say, a million
>simultaneous T1 connections?
>
>*Unbreakable?* Maybe by Joe Hacker. But the technology to break this
>is _precisely_ what the NSA is quite good at, because they've needed
>special tape recorders to record - at once - all the radio signals in
>a large chunk of the radio spectrum for ages.
>
>John Savard
>http://home.ecn.ab.ca/~jsavard/crypto.htm
Exactly. And what do you do when the game gets too rough and you have
to win at any cost. You change the rules. Let's face it, the crypto
obtainable today, implemented properly, based on the information
available, is *really* strong.
The keyspace of just one 256-bit AES key (and I'm just wild-ass
throwing numbers here) is probably something like what a million
satellites could downlink in a million years...
But instead of doing that. Let's just have one source that everyone
uses. Hey, and being the great guys that we are, we'll even provide
the data source. We couldn't possibly keep up with it, so your data
is safe safe safe.
Its the first part of that surreal new play "The Wizard of Ft. Mead"
...pay no attention to the man behind the curtain...
------------------------------
Subject: Re: A different concept for email encryption ??
From: Paul Crowley <[EMAIL PROTECTED]>
Date: Thu, 22 Feb 2001 06:32:53 GMT
Paul Rubin <[EMAIL PROTECTED]> writes:
> Paul Crowley <[EMAIL PROTECTED]> writes:
> > With MIME-style 8-into-6 encoding, 96 bits is 16 characters:
> >
> > [EMAIL PROTECTED]
> >
> > which I think is pretty practical.
>
> How do you use the hash as a public key? I missed something.
You have to look for a key matching the hash in some sort of global
index, as you do with PGP. All that's changed is that you can be sure
you have the correct public key for that email address; it's
infeasable for me to generate a public key matching your email address
and put it on the keyservers.
Yeah, I know it isn't the proposal you were talking about any more; I
was just trying to work out some more practical ideas to the same
broad end.
--
__
\/ o\ [EMAIL PROTECTED]
/\__/ http://www.cluefactory.org.uk/paul/
------------------------------
Subject: Re: Key expansion.
From: Paul Crowley <[EMAIL PROTECTED]>
Date: Thu, 22 Feb 2001 06:32:53 GMT
"Cristiano" <[EMAIL PROTECTED]> writes:
> I have a password constituted from few characters and I want to expand it
> (to at least 128 bits) for use it like session (secret) key for an algorithm
> to symmetrical key (e.g. rijndael). How could I do?
It's best to apply key stretching: read
http://www.counterpane.com/low-entropy.html
Don't worry if the key size of your cipher is larger than the output
of your hash; just pad with zeroes. Or for Rijndael, some
cryptographers recommend padding by repeating the hash output until
the key is full (so if the hash is ABCD but you need ten bytes, use
ABCDABCDAB).
--
__
\/ o\ [EMAIL PROTECTED]
/\__/ http://www.cluefactory.org.uk/paul/
------------------------------
From: [EMAIL PROTECTED] (Mark Healey)
Subject: What does tempest stand for.
Date: Thu, 22 Feb 2001 06:36:06 +0000 (UTC)
I know that "tempest" is an acronym (really T.E.M.P.E.S.T.) but I
forgot what it stands for. Surprisingly this isn't in any of the
online sources I could find.
Could someone please tell me.
Mark Healey
marknews(the 'at' thing)healeyonline.com
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: super-stong crypto, straw man phase 2
Date: Thu, 22 Feb 2001 06:43:28 GMT
Now that you've assimilated my initial straw man, note that the
idea is much the same applied to stream or to block ciphers.
You can express this as another kind of "block chaining mode":
each block encrypts PT plus a new batch of random key bits,
which are (perhaps) shifted into the key register before
encrypting the next block. The idea is to keep injecting
fresh entropy into the channel; note that if the batch size
is nonnegligible, it foils known-plaintext attacks.
------------------------------
From: Robert Davies <[EMAIL PROTECTED]>
Subject: Re: Hardware RNG - Where can I order one?
Date: Thu, 22 Feb 2001 19:47:14 +1300
Reply-To: [EMAIL PROTECTED]
[EMAIL PROTECTED] (Janusz A. Urbanowicz) wrote:
>"The Death" <[EMAIL PROTECTED]> writes:
>
>> Where can i buy a good hardware RNG that i can connect to my PC and use to
>> generate secure random bits?
>
>Get a motherboard that is Intel 810 or 815 based. It has one.
The RNG seems to be on the "Intel 82802 firmware hub". This is sold as
a separate component although is intended to work with the 800 series
chipsets. I don't know whether it is normally included on
mother boards with the 810 or 815 chipset.
Robert
------------------------------
From: [EMAIL PROTECTED] (Vaughan Pratt)
Crossposted-To: sci.math
Subject: Re: Is there an algorithm to sequentially enumerate all transcendental
Date: 22 Feb 2001 06:50:00 GMT
In article <972309$p8l$[EMAIL PROTECTED]>,
Vaughan Pratt <[EMAIL PROTECTED]> wrote:
>
>This leaves open the question of whether there is any alternative to
>diagonalization that is just as elementary. Here's a proof I thought
>of just now (which is no indication of novelty) whose deepest property
>of the reals is that any cut in the real line is closed on one side and
>open on the other.
Now that I look back at some of the previous posts I see my proof
amounts to a simplification of Cantor's 1874 proof replacing the messy
case analysis in the middle-third argument with two sequences advancing
steadily towards each other, each element of which is obtained by
picking the next-enumerated element out of the current interval. It
also replaces the explicit construction of a witness to
nonenumerability by obtaining instead a contradiction with the familiar
"half-closed" property of cuts. And the third-order notion of a
sequence of nested intervals to be intersected is replaced by the
simpler second-order notion of two sequences of endpoints.
While there's no reason to put the middle-third bit back into my
argument, one might at least demand Constructive Correctness. So take
f:N->R to be not a bijection of N with R as I did implicitly but merely
an injection of N into R. If my argument is understood as applying to
the image f(N) (an enumerated set of reals) separating it into two
halves that lie in two disjoint open subsets of R, namely (-oo,b) and
(c,oo) where b is the sup of my left sequence and c the inf of my
right, we then obtain from b <= c that the nonempty interval [b,c] lies
entirely outside f(N). Hence any element of [b,c], say b for
definiteness, serves as a witness to the failure of that particular
attempt to enumerate R. Constructive bliss if you don't mind the extra
work of rounding up this witness.
Note that the only closed interval appearing in my argument is [b,c],
and even that only in the constructive version. In contrast Cantor
builds a nest of closed intervals and then has to deal with their
endpoints, which seems to be the rationale for the middle-thirds stuff
(which does however have the side-effect of forcing b=c, which seems
not to be used however). It would seem simpler just to use open
intervals throughout as in my original nonconstructive argument.
But while Cantor's 1874 argument, or my variant of it, is nice and
short, there remains the really big advantage of Cantor's later
diagonalization argument, that it demonstrates a cardinality jump from
X to 2^X for any set X at all, not just X = N with 2^X ~ R.
Vaughan Pratt
--
My mind and my body keep playing tricks on each other.
When I tell them to cut it out, they just say "Who are you?"
------------------------------
From: [EMAIL PROTECTED] (Hard)
Subject: Re: What does tempest stand for.
Date: Thu, 22 Feb 2001 07:05:04 GMT
On Thu, 22 Feb 2001 06:36:06 +0000 (UTC), [EMAIL PROTECTED] (Mark
Healey) wrote:
>I know that "tempest" is an acronym (really T.E.M.P.E.S.T.) but I
>forgot what it stands for. Surprisingly this isn't in any of the
>online sources I could find.
>
>Could someone please tell me.
>
>Mark Healey
>marknews(the 'at' thing)healeyonline.com
The
Elecronic
Monitors
Providing
Eavesdropping
Spooks a
Target?
------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: Fractal encryption?
Date: Wed, 21 Feb 2001 23:11:40 -0800
Mok-Kong Shen wrote:
>
> "John A. Malley" wrote:
> >
> > http://xxx.lanl.gov/abs/cs.CR/0102012
> [snip]
> > I downloaded it tonight and started reading it. Mr. Ritter's work is
> > cited in the paper.
>
> When you have finished it, would you please explain the
> Eq(2) there? I have difficulty to understand the meaning
> (purpose) of the last three equations in that group.
Well, I finished the paper. Equation 2 reads as pseudocode for a loop:
1. x(n+1) = 4*lambda*x(n)*( 1 - x(n))
2. x'(n+1) = 4*lambda*x'(n)*( 1 - x'(n))
3. P(n) = x(n) XOR x'(n) where P(n) is the chaotic "pseudorandom"
stream
4. C(n) = P(n) XOR plaintext(n) (the authors let y(n) stand for
plaintext(n) in the paper)
so C(n) = x(n) XOR x'(n) XOR plaintext(n)
The variables x(n) and x'(n) are then set with the current values of
x(n+1), C(n) and x'(n+1) as follows:
5. x(n) = x(n+1) XOR C(n) which is the same as x(n) = x(n+1) XOR x(n)
XOR x'(n) XOR plaintext(n);
and
6. x'(n) = x'(n+1).
And then we iterate, back to step 1.
Several things about the paper puzzled me.
First , 0 <= x(n), x'(n) <= 1. As I understand this cipher, the k-bit
representations of x(n) and x'(n) are XORed with k-bit representations
of plaintext(n) but the authors never actually say so in the article.
The cryptanalysis of the cipher did not seem thorough to me. Here are
some things in the paper that prevent me from accepting their results
without question:
if ever x or x' takes on the value of zero, then all subsequent values
of x or x' remain zero and the "perturbation" of one chaotic sequence by
another ceases. P would then just equal either x or x' from that point
on and the "mixing" of two chaotic sequences ceases. This phenomenon is
not mentioned in the paper and neither are its effects on the
cryptanalysis of the cipher.
and
in section 4.4 of the paper, the authors state that P(n) and P(n+1) will
never both be all zero bits if the plaintext(n) to be enciphered is
never all zero bits. They claim "a null vector has no information
content and is never transmitted." This is odd to me. We cannot rule
out a block of all 0 bits in the plaintext - image files and binaries,
for example, can have "long" strings of 0s in them. What is the effect
of a long string of all-0 plaintext on the cryptanalysis of the cipher?
and
what is the effect of the finite resolution (number of bits)
representing x and x' on the cryptanalysis of the cipher? Are there any
repeating cycles in the lower-order bits of a k-bit representation of x
and x' as the cipher executes?
It's an interesting idea, mixing chaotic sequence this way, but I don't
trust using it without seeing more rigorous cryptanalysis.
Just some random thoughts,
John A. Malley
[EMAIL PROTECTED]
------------------------------
** 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
******************************
