Cryptography-Digest Digest #230, Volume #9 Sat, 13 Mar 99 18:13:03 EST
Contents:
Is TEA Algorithm safe???? ("melih")
Re: Quantum PRNG ("Trevor Jackson, III")
Re: Crypto transmission in noisy ambient (Christopher)
Re: ElGamal vs RSA (Michael Sierchio)
Re: ElGamal vs RSA (Michael Sierchio)
Re: Client-server encryption key negotiation...? (Michael Sierchio)
(in)Secure Socket Layer? (Roy Sigurd Karlsbakk)
Re: Quantum Computation and Cryptography (Tom Knight)
Re: Self-executing encryption program (Sundial Services)
Re: Quantum PRNG (R. Knauer)
Re: ElGamal vs RSA ("Roger Schlafly")
Re: SHA algorithm (iLLusIOn)
Re: Is TEA Algorithm safe???? ("Alex")
no use! ([EMAIL PROTECTED])
The Magic Screw, Non-Secret Encryption, and the Latest WIRED
Re: prob. of a given subsequence in a sequence ("almis")
Re: How do i compute (a^b) mod n (Paul Schlyter)
Re: How do i compute (a^b) mod n (Paul Schlyter)
Re: prob. of a given subsequence in a sequence ("almis")
----------------------------------------------------------------------------
From: "melih" <[EMAIL PROTECTED]>
Subject: Is TEA Algorithm safe????
Date: Sat, 13 Mar 1999 14:22:54 -0000
Can anyone tell me if TEA algorithm is safe (I am told it is not safe
however the reason as to why is what I am after).
If not, does TEA Extensions solve the problems that made the TEA unsafe?
Thanks for your help.
Melih
------------------------------
Date: Sat, 13 Mar 1999 11:01:53 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Quantum PRNG
Andrew Wall wrote:
>
> Christopher wrote in message ...
> >In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
> <snip>
>
> <snip>
> >It seems to me the only thing that would make it a better choice is if
> >it's proven that attacking the seed is easier then studying its output.
> >BTW, how do the other PRNGs fit here. I've seen mention of generators
> >with extremely large cycles (256 bit), if only the least significant byte
> >of one of these is used (making 31 bytes hidden internal state) is it
> >probable that figuring the state from a stream is as much work as guessing
> >the seed?
> >
>
> I would like to know what quality of a hardware PRNG would be.
> What if you built one with a large amount of non-volatile memory to hold its
>internal state that produced numbers all the time?
> Whenever it was powered on, it produced numbers whether you wanted them or not.
> I propose that no-one could guess better than 1/2^N (where N is the number of bits
>in the memory) what the internal state was and
> therefore what the next number would be.
> If you only take numbers when you want them, you are introducing a true random
>factor also.
> Would this then qualify as a TRNG?
No. You must assume that the algorithm by which the internal states
evolves is known to an adversary. A congruential generator, like the
merseene twister, or an LFSR generator will quickly betray the internal
state. An adversary intercepting a tiny fraction of the full cycle
length, usually only a few time the size of the internal state, can
deduce the internal state after which he can predict all future states.
In fact, he can usually run the generator backward to recover previous
states as well.
This problem stems from the fact that any such generator is
deterministic. Knowing one state allows you to calculate the complete
sequence of states. This is the exact opposite of what is desired:
interderminism / unpredictability / independence.
>
> Andrew Wall
------------------------------
From: [EMAIL PROTECTED] (Christopher)
Subject: Re: Crypto transmission in noisy ambient
Date: Sat, 13 Mar 1999 02:09:40 -0500
In article <[EMAIL PROTECTED]>, moc.lis@elyalp <- Reverse
if replying by Email! wrote:
|:| On Thu, 11 Mar 1999 22:01:28 -0200, "F. Arndt" <[EMAIL PROTECTED]>
|:| wrote:
|:|
|:| >A low-power but strongly encrypted (RSA or ElGamal) exchange in the
|:| >presence of noise AND interference, such as often prevails in wireless
|:| >comm, would seem to be problematical.
|:|
|:| Why not use the "confusion sequence" from a stream cipher as the
|:| "spread code" for a spread-spectrum wireless link? This would be
|:| hard to receive correctly (or even detect!) without the key but
|:| shouldn't increase the BER...
|:| any thoughts?
I'm not familiar with the "confusion sequence," but if someone with a
spectrum analyer isn't getting any info on the key, great.
If it's for a "simple" FM transmission, using a sideband for multi-bit
error correcting codes comes readily to mind.
--
It's easier to judge a book by its cover knowing nothing of its contents.
------------------------------
From: Michael Sierchio <[EMAIL PROTECTED]>
Subject: Re: ElGamal vs RSA
Date: Sat, 13 Mar 1999 10:12:43 -0800
Reply-To: [EMAIL PROTECTED]
[EMAIL PROTECTED] wrote:
> > For a given key size, DH over GF(2^n) is
> > slight less secure than RSA, but users can compensate for this by
>
> No!!! It is significantly less secure. DL over GF(2^1024) is almost
> within reach now. DL over GF(p) where p is an odd 1024-bit prime is NOT
> in reach.
Bob -
My news host is expiring these posts faster than I can read them --
I may have missed something.
Can you answer the following:
If you select a large p for GF(p), does the choice of
a generator g for g^x mod p matter, so long as it is
a generator of GF(p)? It's often said that it is not
necessary for g to be a generator of the whole field,
but it is better.
Why (esp. when 2 is used as a generator) is p selected
such that (p-1)/2 is also prime?
------------------------------
From: Michael Sierchio <[EMAIL PROTECTED]>
Subject: Re: ElGamal vs RSA
Date: Sat, 13 Mar 1999 10:13:43 -0800
Reply-To: [EMAIL PROTECTED]
Daniel Bleichenbacher wrote:
>
> RSA has definitively the advantage over ElGamal encryption/signatures
> that good standards for RSA (IEEE, ANSI, PKCS) are available.
Bingo.
> When no standard is available people design there own ad-hoc schemes,
> and usually there are enough pitfalls to go wrong.
Ditto.
------------------------------
From: Michael Sierchio <[EMAIL PROTECTED]>
Subject: Re: Client-server encryption key negotiation...?
Date: Sat, 13 Mar 1999 10:15:06 -0800
Reply-To: [EMAIL PROTECTED]
Paul Pedriana wrote:
>
> Say you have a client and server on a network and they
> want to start a secure communication between each other.
> It makes sense to me that the client and server can
> communicate with encrypted data to prevent others from
> reading the communications.
see the SSLv.3 and http://www.skip.org/
------------------------------
From: Roy Sigurd Karlsbakk <[EMAIL PROTECTED]>
Subject: (in)Secure Socket Layer?
Date: Sat, 13 Mar 1999 19:36:42 +0100
Hi all
After the DES-III contest
(http://www.rsa.com/pressbox/html/990119-1.html), I thought about this
so-called non-domestic SSL. Using 40 bit encryption (128 bit RC-4 with a
40 bit encryption key - the rest of the bits padded with zeros) seems to
me quite a little effort to crack. I just asked myself the following
questions:
DES-56 was brute-forced in 22 hours and 15 minutes = 80100 seconds.
40-bit whatever algorithm is 16 bit less hard to brute force
16 bit = 65535
40-bit encryption could be broken in a matter of seconds (80100 / 65535
= 1,22) using the same computer power as in the DES-III contest.
1. Is this bull? Or am I right? I know far to little about cryptography
to know
2. Are there any software around that could help me try to brute-force
this so-called "SSL"?
Please CC: to me when answering to the group.
Thanks in advance
Roy
------------------------------
From: Tom Knight <[EMAIL PROTECTED]>
Subject: Re: Quantum Computation and Cryptography
Date: 13 Mar 1999 11:57:27 -0500
I'm sorry I'm coming late into this discussion. Some might be amused
to see how one can compute dissipationlessly with conventional cmos
technology
http://www.patents.ibm.com/details?pn=US05378940__&language=en
We're constructing a fully reversible, (asymptotically)
dissipationless computer using this technique in my research group.
[EMAIL PROTECTED] (Bill Unruh) writes:
> Nand gates cannot be reversible. You can create a gate with two output
> channels which is reversible. But nothing which takes two inputs and
> produces one output can ever be reversible.
You have to be careful here. The issue is whether you throw away the
bits on the input of the NAND gate. Surely what you say is correct if
you throw those bits away, but if you retain copies of the input bits,
then a NAND (or any function!) is reversible, since I can compute it
again and use the result of the second computation to erase the data.
I'd recommend Bennett's "Thermodynamics of Computation -- A Review"
for people interested in this topic.
------------------------------
Date: Sat, 13 Mar 1999 12:39:54 -0700
From: Sundial Services <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Self-executing encryption program
Mycroft wrote:
>
> "Bo Dömstedt" wrote:
>
> > [EMAIL PROTECTED] wrote:
> > >Does anyone know of an encryption program that creates self-executing
> > >decryption files, so you can send files to anyone who doesn't have the
> > >program, as long as they have a password?
>
> Pkzip has a "scramble" option and you can create self-extracting
> executables
> with it.
[Snicker...] Do you know how long it actually takes to dismantle the
PKZip stream cipher? If you have the slightest idea of what as little
as 12 bytes of the original plaintext was, at any point in the
enciphered stream, then you can compute the internal key and recover the
information remarkably quickly. This fact is all-too-well known.
I'm sure that tools to build self-decrypting archives that feature
strong[er] encryption must exist by now. Most encryption programs
routinely compress the data before enciphering it, often using PKZip's
algorithms, but then apply stronger cryptography to it and I don't
recall any that make self-extracting files. (Surely I'm overlooking
them, however.)
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Quantum PRNG
Date: Sat, 13 Mar 1999 19:56:59 GMT
Reply-To: [EMAIL PROTECTED]
On Sat, 13 Mar 1999 11:01:53 -0500, "Trevor Jackson, III"
<[EMAIL PROTECTED]> wrote:
>No. You must assume that the algorithm by which the internal states
>evolves is known to an adversary. A congruential generator, like the
>merseene twister, or an LFSR generator will quickly betray the internal
>state. An adversary intercepting a tiny fraction of the full cycle
>length, usually only a few time the size of the internal state, can
>deduce the internal state after which he can predict all future states.
>In fact, he can usually run the generator backward to recover previous
>states as well.
>
>This problem stems from the fact that any such generator is
>deterministic. Knowing one state allows you to calculate the complete
>sequence of states. This is the exact opposite of what is desired:
>interderminism / unpredictability / independence.
It would seem that the correct approach when using a PRNG with a
stream cipher would be to mix the keystream in such a way to make it
very difficult to learn anything about the internal state of the PRNG.
Even then the main problem with PRNG-based ciphers (stream or block)
is that the small key (or seed) for the PRNG makes having more than
one intelligible plaintext as a valid decryption nearly impossible if
the message is significantly longer than the key.
Bob Knauer
"My choice early in life was either to be a piano-player in a whorehouse
or a politician. And to tell the truth there's hardly any difference."
-- Harry Truman
------------------------------
From: "Roger Schlafly" <[EMAIL PROTECTED]>
Subject: Re: ElGamal vs RSA
Date: Sat, 13 Mar 1999 12:15:22 -0800
Michael Sierchio wrote in message <[EMAIL PROTECTED]>...
>Daniel Bleichenbacher wrote:
>>
>> RSA has definitively the advantage over ElGamal encryption/signatures
>> that good standards for RSA (IEEE, ANSI, PKCS) are available.
>
>Bingo.
This is really a silly statement. The standardization work in ANSI and
IEEE for ElGamal-like signatures predated that for RSA. The most
popular ElGamal variant is commonly called DSA. As Johnson pointed
out, there are perfectly good standards for DSA and there have been
for years.
Bleichenbacher knows this, but argues that DSA and ECDSA are
"derivated algorithms", while PKCS #1 version 1.5. I am not sure this
distinction makes any sense, but it is useless even if it does.
------------------------------
Date: 13 Mar 1999 20:18:17 -0000
From: iLLusIOn <Use-Author-Address-Header@[127.1]>
Subject: Re: SHA algorithm
=====BEGIN PGP SIGNED MESSAGE=====
>Pad out that first block with the initial 1 bit and then 0's all the
>way to 512 bits, then the next block with 0's to 512-64=448 bits, then
>add your 64-bit count at the end of the second block. That's the first
>point at which you can stop 64 bits short of a multiple of 512.
ok thanks. just one last thing I'm unsure about, if the message is
exactly 512 bits - I assume that I'd have to add a 2nd block consisting
of 1 x bit 1, 447 x bit 0, 64 x message length, am I right? or can I
just leave this 2nd block away if the message is exactly 512 bits?
TIA,
//iLLusIOn
~~~
This PGP signature only certifies the sender and date of the message.
It implies no approval from the administrators of nym.alias.net.
Date: Sat Mar 13 20:18:15 1999 GMT
From: [EMAIL PROTECTED]
=====BEGIN PGP SIGNATURE=====
Version: 2.6.2
iQEVAwUBNurICE5NDhYLYPHNAQFgOwf+KI16r5T10ebQEyU6sLX4mzlml52Rh9Xg
fzvXhyLxulpSGX3niz1rhnAmirtB+mbcQr+G0l8jNU6ZNOGj+g3glKyNlmYnIe3Z
JHQzPyS3nTR8htKvULXvGdCjVHNU8nbC3YDFYAsUHehRoUKm87w7UJn5gFdJo0wp
KgXLTEeqJXto0zvUax5ZFhiauDg607hnVxSGjjUKCBos6qPihkb5Az8lW02aYJ/M
Pkj5aTLuCCUpf3tzftx03/r3pb+cCIc5XOFkMmgBnJbhZXqxeYJio7DsKsruJoCe
di3KNnXVu38LAwc4BviD9zgNq4qipb6ksmra8AJbP5sROQqwgbSIMw==
=DoO9
=====END PGP SIGNATURE=====
------------------------------
From: "Alex" <[EMAIL PROTECTED]>
Subject: Re: Is TEA Algorithm safe????
Date: Sat, 13 Mar 1999 23:03:12 +0300
>Can anyone tell me if TEA algorithm is safe?
TEA stand for "Tiny Encryption Algorithm". No comments.
Regards,
Alex.
------------------------------
From: [EMAIL PROTECTED]
Subject: no use!
Date: Thu, 11 Mar 1999 11:45:47 +0100
..where are these from...;-)
http://members.tripod.com/lol_ta/
------------------------------
From: [EMAIL PROTECTED] ()
Subject: The Magic Screw, Non-Secret Encryption, and the Latest WIRED
Date: 13 Mar 99 20:26:56 GMT
The latest issue of WIRED magazine, with a black cover in honor of Y2K,
has an article by Steven Levy about the British invention of public-key
cryptography.
This article adds quite a bit to what was in a paper on the subject
available on the WWW that was mentioned in a post here (there's a pointer
to it on Frode Weierud's site) some time ago.
The main thing new in the article is the revelation that there was great
nervousness at the GCHQ about the very thing I've expressed concern in
some of my early posts: that there could be a mathematical discovery that
would vitiate the security of RSA, Diffie-Hellman, and other public-key
ciphers, because they rely on a narrow range of techniques.
Even more sensitive, the revelation that one wasn't found by 1977 when the
technique was publicly discovered.
And, because of this concern, I expressed some doubt that, as some books
have claimed, that the STU-III or other current advanced encryption
equipment would operate without key material in the manner of a copy of
PGP. But I noted that one could still use public-key techniques, even if
one doesn't fully trust them, as one leg of a 'triad', to use a term from
nuclear defense terminology. And so, I will summarize a point I tried to
make in another post some time ago:
Key hidden in hardware - compromised through reverse-engineering of
captured hardware.
Key loaded by personnel - vulnerable through suborning of personnel.
Key generated and used via public-key mechanisms - vulnerable through
mathematical advances.
If you're handling military secrets, use all three mechanisms - each one
with a key big enough so that if one of the three keys only remains
secure, your communications are secure. If the 'big boys' _aren't_ doing
this, they should start thinking about it.
John Savard
------------------------------
From: "almis" <[EMAIL PROTECTED]>
Subject: Re: prob. of a given subsequence in a sequence
Date: Sat, 13 Mar 1999 13:29:33 -0600
Gustavo wrote in message <7c8p2s$aup$[EMAIL PROTECTED]>...
|Hi everyone.
|I would like to know how to compute the probability
|that a given subsequence of length S is part of a
|larger random sequence of length L.
|It seems that the probability depends on the sub-
|sequence (maybe on its autocorrelation properties?)
|but I have not been able to find the relation yet.
|Thank you very much for any help.
|Gustavo
|
|
Nice Question!
It's early, just started my coffee and I'm trying to watch a ball game.
But I'm putting my money on:
(L - S + 1) / 2 ^ S
...al
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: How do i compute (a^b) mod n
Date: 13 Mar 1999 22:39:39 +0100
In article <7c9re0$vm0$[EMAIL PROTECTED]>,
Luke Herbert <[EMAIL PROTECTED]> wrote:
> solution to my own problem:
>
> As x*x mod n = (x mod n)*(x mod n) the following loop will do it
>
> xmn := x mod n;
> result := xmn;
> for i := 2 to y do result := (result * xmn) mod n;
>
> there is no owerflow if n^2 is less than maxlongint;
But this method is VERY slow for large y. The one below is much
faster. In pseudo-C it becomes:
INTEGER expmod( INTEGER x, INTEGER y, INTEGER m )
{
INTEGER res = 1;
INTEGER xx = x;
while( y > 0 )
{
if ( odd(y) )
{
res = res * xx mod m;
}
xx = xx * xx mod m;
y = y / 2;
}
return res;
}
and in real C it becomes:
typedef int INTEGER;
INTEGER expmod( INTEGER x, INTEGER y, INTEGER m )
{
INTEGER res, xx;
for( res=1, xx=x; y > 0; xx=xx*xx%m, y/=2 )
{
if ( y & 1 )
res = res * xx % m;
}
return res;
}
INTEGER can be typedef'ed as long, or long long, if needed. In C++
INTEGER can be typedef'ed as some BigInt class.
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: [EMAIL PROTECTED] [EMAIL PROTECTED] [EMAIL PROTECTED]
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: How do i compute (a^b) mod n
Date: 13 Mar 1999 22:40:10 +0100
In article <7c9rfm$vmt$[EMAIL PROTECTED]>,
Luke Herbert <[EMAIL PROTECTED]> wrote:
> This way springs to mind:
>
> function xtoymodn(x,y,n:integer):integer;
> var result,mult,lp:integer;
> begin
> mult:= x mod n;
> result:=1;
> if mult=0 then result:=0
> else if mult=1 then result:=1
> else if mult=-1 then result:=1-2*(y mod 2)
> else for lp:= 1 to y do result:=(result*mult) mod n;
> xtoymodn:=result;
> end;
>
> I imagine it's not the most efficient implementation possible; perhaps
> diving into a number theory textbook would provide some sneakier
> methods.
Below a more efficient algorithm is given, in pseudo-C:
INTEGER expmod( INTEGER x, INTEGER y, INTEGER m )
{
INTEGER res = 1;
INTEGER xx = x;
while( y > 0 )
{
if ( odd(y) )
{
res = res * xx mod m;
}
xx = xx * xx mod m;
y = y / 2;
}
return res;
}
and in real C it becomes:
typedef int INTEGER;
INTEGER expmod( INTEGER x, INTEGER y, INTEGER m )
{
INTEGER res, xx;
for( res=1, xx=x; y > 0; xx=xx*xx%m, y/=2 )
{
if ( y & 1 )
res = res * xx % m;
}
return res;
}
INTEGER can be typedef'ed as long, or long long, if needed. In C++
INTEGER can be typedef'ed as some BigInt class.
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: [EMAIL PROTECTED] [EMAIL PROTECTED] [EMAIL PROTECTED]
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: "almis" <[EMAIL PROTECTED]>
Subject: Re: prob. of a given subsequence in a sequence
Date: Sat, 13 Mar 1999 16:40:40 -0600
I told you it was early, I hadn't had my coffee and the ball game was pretty
good.
(It's still on)
Anyway :
1) Notice that the probability of success when L = S is 1 / 2^S
2) Solve the following problem:
Given that the probability of success of one try is 1 / 2^S,
What is the probability of at least one sucess in L - S tries ?
I think it's:
p = 1 - (1 - 1 / 2^S)^(L - S + 1)
...al
------------------------------
** 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 (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
