Cryptography-Digest Digest #751, Volume #13 Mon, 26 Feb 01 13:13:01 EST
Contents:
Re: Fair(er)play (Daniel)
Re: How to find a huge prime(1024 bit?) ("Jakob Jonsson")
Re: Improved stream cipher? (was: Re: Simple, possibly flawed, stream cipher)
("Henrick Hellström")
Signature in Merkle-Hellman system ("mklai")
Rijndael S-box inverse (Panu =?iso-8859-1?Q?H=E4m=E4l=E4inen?=)
Open-SSH and RNGs ([EMAIL PROTECTED])
Re: RSA - public key exponents and plain text. (DJohn37050)
Re: Rijndael S-box inverse ("Jeffrey A. Six")
Re: Signature in Merkle-Hellman system ("Roger Schlafly")
Re: Rnadom Numbers ("Douglas A. Gwyn")
Re: super-stong crypto, straw man phase 2 ("Douglas A. Gwyn")
Re: Life cycle of keys ("Douglas A. Gwyn")
Re: Random number encryption ("Douglas A. Gwyn")
Re: how long can one Arcfour key be used?? ("Simon Johnson")
Re: Super strong crypto ("Douglas A. Gwyn")
Help Please !!!!!!!!!!!! (PADDOCK)
Re: Super strong crypto ("Douglas A. Gwyn")
Re: "RSA vs. One-time-pad" or "the perfect enryption" ("Douglas A. Gwyn")
Re: Help Please !!!!!!!!!!!! (Volker Hetzer)
Re: The Key Vanishes (fwd) (Darren New)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Daniel)
Subject: Re: Fair(er)play
Date: Mon, 26 Feb 2001 10:08:44 GMT
On 25 Feb 2001 22:19:18 GMT, [EMAIL PROTECTED] (JPeschel)
wrote:
>An example from www.ecoo.org/sigcs/finals/fin1994p4.html.
This should read :
An example from www.ecoo.org/sigcs/finals/fin1999p4.html
^^
best regards,
Daniel
------------------------------
From: "Jakob Jonsson" <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp
Subject: Re: How to find a huge prime(1024 bit?)
Date: Mon, 26 Feb 2001 11:19:36 +0100
It is true that the primes will not be uniformly chosen if incremental
search is used. Yet, Brandt and Damgård have shown that this bias does not
affect security; see
J. Brandt and I. Damgård. On generation of probable primes by incremental
search. In Advances in Cryptology - Crypto'92, pages 358-370.
Springer-Verlag, 1993.
PGP 2.6.3i for PC uses incremental search (it starts with a number congruent
to 3 modulo 4 and increments in steps of 4). It doesn't apply the
Miller-Rabin test; instead, it checks whether x^{p-1} == 1 (mod p) for p =
2,3,5,7. (At least this was true for the source code I examined back in
1997.)
Jakob
"Thomas Boschloo" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> [CC-ed: to sci.crypt for a professional opinion]
>
> An Metet wrote:
>
> > >How to find a huge prime(1024 bit?)
> >
> > Select a big random number, try to divide it by small numbers
> > first, then search for `Rabin-Miller´ primality test at google. If that
> > fails, increase the number and repeat the above.
>
> I would disagree, although I am no scientist.
>
> Primes get very sparse at high numbers, but you just never know how far
> appart they will be. There might be vast spaces without any primes
> followed a few primes that are very near together.
>
> If you use your proposed algorithm (and I sure as hell hope that PGP
> 2.6.3i doesn't use this methode), you will be more likely to hit the
> first prime after a large space without primes, than you will be to hit
> the prime just after that. Thus you (radically?!) reduce the maximum
> ammount of primes you are likely to find.
>
> The correct implementation would be to just generate a *new* prime from
> scratch, preferably with (some) new entropy added to your pool (maybe
> task-switching/runtime info?). It will be a lot slower I guess,
> gathering all that entropy and calculating all those MPI random numbers.
> But the resulting key will be a lot better IMHO!
>
> > Also check out the Science->Math->Number Theory->Primes section
> > while you are at google.
>
> Hmm, maybe I can produce some high-school level proof of my
> assumptions..
>
> First: The density of primes is at average N/ln(N) from 2 until N IIRC
> (where N is e.g. a 512 bit number you will need for your P and Q).
>
> Second: Nope. I can't produce some examples at this (late) time of a few
> consecutive primes above some large (chosen) number.
>
> The Greek however proved that if you had some 'largest' prime number,
> you could just multiply all primes until that prime number, add one and
> then you would have created a prime that was even 'larger'. So there is
> an endless supply of primes (although they may become a little far
> appart or they might become hard to 'prove' to be prime).
>
> Thomas
> --
> Jessica "I'm not bad, I'm just drawn that way"
>
>
------------------------------
From: "Henrick Hellström" <[EMAIL PROTECTED]>
Subject: Re: Improved stream cipher? (was: Re: Simple, possibly flawed, stream cipher)
Date: Mon, 26 Feb 2001 11:58:59 +0100
"David Wagner" <[EMAIL PROTECTED]> skrev i meddelandet
news:97ca74$dta$[EMAIL PROTECTED]...
> Henrick Hellström wrote:
> >Here is a similar cipher that shouldn't be vulnerable to Scott Fuhler's
> >attack. These are the changes:
> >
> >* Instead of initializing x to 1, x is initialized to state[7].
> >* Instead of adding either 0 or 1 to state[i] depending on a single bit
of
> >x, x is added to state[i].
> >* In order to prevent attacks that exploit differential relations on
> >state[i], the state array is shifted up one byte and state[0] is set to
the
> >value of the cipher text.
>
> I'm still left wondering about a comment I made earlier.
> It appears that such a cipher requires at least 8 table
> lookups per byte of output (as well as a few other very
> simple operations).
>
> How does this cipher compare in speed to, say, RC4 or
> SEAL? Does anyone have any performance measurements?
I haven't tried to do implement it in assembler, so I couldn't say. I
estimate that the cipher is slower than RC4, provided that the RC4
implementation I have is correct: A two byte internal state is updated for
each byte, and is used to permute the 256-byte bijective SBox.
However, I wouldn't use RC4 for a number of reasons, but most importantly
because of it's key set up scheme which is bound to result in key
collisions, and, together with it's similarty to the state update function,
in key proximity.
> If this is slower than RC4 and SEAL, is it worth spending
> a lot of time on?
It would at least be educational. And I would not claim that RC4 and SEAL
are state of the art top secure ciphers.
> Also, my earlier comments about the insecurity of using
> a 64-bit state still apply. With X bytes of known text,
> one can break the cipher with 2^64/X work, and for X = 1MB,
> this is a disconcertingly low security level. There are
> also precomputation-based speedups (e.g., Hellman's
> time-space tradeoff) that should not be ignored.
This is an interesting question: Does the 2**64/X estimation hold for PCFB
mode ciphers? I would appreciate a working code
sample that proves this.
--
Henrick Hellström [EMAIL PROTECTED]
StreamSec HB http://www.streamsec.com
------------------------------
From: "mklai" <[EMAIL PROTECTED]>
Subject: Signature in Merkle-Hellman system
Date: Mon, 26 Feb 2001 05:00:52 -0800
This may be a novice question. And it may not of practical interest because
the Merkle-Hellman knapsack cryptosystem has long been broken.
The title of Merkle and Hellman's paper is "Hiding Information and
*Signatures* in Trapdoor Knapsacks." But I read from a book that the
Merkle-Hellman knapsack cryptosystem cannot be used for authentication.
"The reason is that the enciphering transformation does not map the entire
message space back onto itself; thus, it is not possible to take an
arbitrary message and sign it by applying the deciphering transformation."
So, what kind of "signatures" was the Merkle-Hellman paper talking about?
Thanks.
------------------------------
From: Panu =?iso-8859-1?Q?H=E4m=E4l=E4inen?= <[EMAIL PROTECTED]>
Subject: Rijndael S-box inverse
Date: Mon, 26 Feb 2001 16:30:34 +0200
In Rijndael specification and some other papers it has been stated that Rijdael
encryption and decryption can share the S-boxes. Assuming that I have the
encryption S-box, how can I use this to produce the inverse S-box?
-- Panu Hämäläinen
------------------------------
From: [EMAIL PROTECTED]
Subject: Open-SSH and RNGs
Date: Mon, 26 Feb 2001 15:18:41 GMT
Hi,
I have a small cluster of UNIX machines (1 Solaris 2.5.1 and 2
Linux), and I am trying to set up Open-SSH (2.3.0p) on the Solaris
machine. I am finding that the process of generating entropy (using
ssh_prngs_progs) is painfully slow, much slower than an old version of
Open-SSH which I compiled to use egd.pl. I was wondering if there was
anything wrong with:
1) editing the ssh_prng_progs file to only (first ?) call the egd.pl
socket
2) editing egd.pl to have it start by calling /dev/urandom on the 2
Linux machines.
I hope I'm not asking in the wrong place. If so, my apologies.
Gord
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Date: 26 Feb 2001 15:51:36 GMT
Subject: Re: RSA - public key exponents and plain text.
You should read IEEE 1363 on RSA encryption, there are LOTS of pitfalls to
avoid. Use of a not too low exponent is considered by some to be one way of
avoiding some of them, or at least a conservative precaution.
Don Johnson
------------------------------
From: "Jeffrey A. Six" <[EMAIL PROTECTED]>
Subject: Re: Rijndael S-box inverse
Date: Mon, 26 Feb 2001 10:44:39 -0500
you don't. use the same box.
-j6
"Panu Hämäläinen" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> In Rijndael specification and some other papers it has been stated that
Rijdael
> encryption and decryption can share the S-boxes. Assuming that I have the
> encryption S-box, how can I use this to produce the inverse S-box?
>
> -- Panu Hämäläinen
------------------------------
From: "Roger Schlafly" <[EMAIL PROTECTED]>
Subject: Re: Signature in Merkle-Hellman system
Date: Mon, 26 Feb 2001 16:18:16 GMT
"mklai" <[EMAIL PROTECTED]> wrote in message
news:97dk0f$q3d$[EMAIL PROTECTED]...
> This may be a novice question. And it may not of practical interest
because
> the Merkle-Hellman knapsack cryptosystem has long been broken.
> The title of Merkle and Hellman's paper is "Hiding Information and
> *Signatures* in Trapdoor Knapsacks." But I read from a book that the
> Merkle-Hellman knapsack cryptosystem cannot be used for authentication.
> "The reason is that the enciphering transformation does not map the entire
> message space back onto itself; thus, it is not possible to take an
> arbitrary message and sign it by applying the deciphering transformation."
> So, what kind of "signatures" was the Merkle-Hellman paper talking about?
The critical issue is the "density" of the image. A density of 90% would
mean
that there is an easily parameterized message space such that 90% of the
messages are the enciphed messages for some plaintext. Ie, the enciphering
transformation hits 90% of the target space.
If the density were 90%, then you could do signatures 90% of the time.
Actually the Hellman-Merkle density was more like 1%, altho they had
a footnote claiming to have ideas for doing better.
A density of 1% is still manageable. You could put a random 4-byte block
header into your message to be signed, and vary that until signing is
successful.
Maybe it would take 100 tries on average. Hellman-Merkle signatures were
pretty fast, so this was viable.
Historically, this was before RSA, I believe. Hellman and Diffie had already
invented an efficient public key encryption system, and getting signatures
was the big open problem. Hellman-Merkle (and Stanford) got a patent
that claimed any use of public key signatures based on this knapsack work.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Rnadom Numbers
Date: Mon, 26 Feb 2001 16:55:57 GMT
Simon Johnson wrote:
> yeah, good point. I assume that this question cannot be answered then until
> the problem surrounding p=np is solved, right?
P?=NP has absolutely nothing to do with whether a PRNG output can
be successfully cryptanalyzed.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: super-stong crypto, straw man phase 2
Date: Mon, 26 Feb 2001 17:08:32 GMT
William Hugh Murray wrote:
> I agree to both points. However, I was not addressing either. Rather, I was
> addressing the claim that differential cryptanalysis was a cheap tool.
I don't recall seeing anybody saying that. So-called differential
cryptanalysis is a *weak* tool -- look at its input requirements.
In addressing issues of absolute strength of encryption, discussion
about DC properties is rather pointless (except to establish an
upper bound that is not all that different from what one gets by
considering brute-force searching of the key space).
> > For all we know, some government agency *could* have much better
> > cryptanalytic techniques against DES than the public know of.
> However unlikely it is that anyone could keep such a secret, ...
As a general observation, you're mistaken. It *might* be hard to
keep the lid on a proof of P=NP or some other breakthrough with
important ramifications to a huge public field of study, but the
lid has been kept on a *large* number of advanced cryptanalytic
techniques.
> ... Nonetheless, if modern cryptography is the weak link in your
> security, then you are very secure indeed. I do not need proof
> for that assertion.
The guys down the street must be rolling in the aisles at that one.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Life cycle of keys
Date: Mon, 26 Feb 2001 17:21:00 GMT
Mok-Kong Shen wrote:
> How many MB can one safely encrypt with AES and a single
> (random) key of 128 bits?
Even if one picks parameters to make it a more precise question,
how to determine the answer is not publicly known. You also
need to consider the case where multiple messages have been
encrypted using the same key, where there is a large amount of
known plaintext, etc. In the simple case where there is just
one continuous channel, public expert opinion appears to be that
an arbitrarily large amount of ciphertext could be produced from
controlled plaintext (more severe attack than known plaintext)
without anybody being able to recover the key using available
resources. But that's opinion, not proven.
> finally the opponent: The combined entire resources of
> the topmost (most capable) one dozen angencies of the
> (democratic and non-democratic) world.
You are not going to get an accurate answer to that in a
public forum. If you only take into account their estimated
computing capacity but assume a stupid method of attack, it's
rather pointless, since that's not what they would actually
use that equipment for.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Random number encryption
Date: Mon, 26 Feb 2001 17:24:49 GMT
Tim Tyler wrote:
> Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
> : Indeed, if you could deliver N bits of key securely, why not
> : just use that capability to send the N-bit message immediately.
> In the cases where it is used, the answers to that question ...
Yes, there are occasional legitimate applications for OTP.
However, my comment was meant to help enlighten the asker.
Other things being equal, using OTP for encryption just
trades one problem for another similar one.
------------------------------
From: "Simon Johnson" <[EMAIL PROTECTED]>
Subject: Re: how long can one Arcfour key be used??
Date: Mon, 26 Feb 2001 17:31:14 -0800
Julian Morrison <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> How much info is it safe to encode with the one key in Arcfour? Assuming
> one is using the full 256 bytes possible as key+IV.
>
> One of my intended designs involves DH exchanging a key, building an
> Arcfour state at both ends from it, and then using that to exchange data.
> In other words, not starting from Arcfour key setup every time, but just
> picking up the state where it left off. I assume there's some limit how
> long I can go on doing this before it gets insecure and I need to exchange
> keys again, hence my question above.
I think I remember for an average key it is something like a few gigabytes
before a bias can be detected in the output. Not sure if this is correct
though?
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Super strong crypto
Date: Mon, 26 Feb 2001 17:34:10 GMT
Nicol So wrote:
> ... Ideally the TEKs, if related to one another at all,
> should be so related that knowledge of one (together with
> intercepted traffic) would not allow easy derivation of
> the others.
There were other comments too..
Check the other thread for a specific set of parameters
as a representative example.
As to key recovery, my working assumption is that we are
trying to figure out what form a realization of the subject
(super strong crypto) might take. *If* one has a basic
(e.g. block encipherment) component suitable for use in
such a scheme, then there is negligible chance that any
isolated key could be recovered. My straw man proposal
takes that as a starting place and build on it in an
attempt to avoid the obvious theoretical weakness of
stretching a small amount of key information over a long
span of encryption, as is often done in current (public)
systems. The suggestion is that something of the sort
might be a necessary component of any practical "super
strong crypto" system.
------------------------------
From: PADDOCK <[EMAIL PROTECTED]>
Subject: Help Please !!!!!!!!!!!!
Date: Mon, 26 Feb 2001 17:27:51 -0000
the following is a list of unix crypt passwords
have broken 15 of them using John the ripper and crack etc
but can't get the rest - any ideas u clever bods?
(and no, this is not for anything illegal!)
thanks
a novice
nbr:NgrdOQvGJxApM:Brian Randell
nim2:PZ.Gm3kItDUbo:Isi Mitrani
nsks:r/3cSTl4rxPSo:Santosh Shrivastava
npal:kS6W7H2qpQhYY:Pete Lee
nta:PndNNaaMSMhOQ:Tom Anderson
ncbj:6RERTsaF2WR1U:Cliff Jones
nay:Y709XJm2HUfx6:Alex Yakovlev
nmk:JgcQaXcjborkI:Maciej Koutny
njll:8cV7NUYoDXjkY:John Lloyd
npw:u4kASSO9cX0No:Paul Watson
nrjs:BOaxJuED4sH5w:Robert Stroud
ncp:Nn9Zpg0p7d.b2:Chris Phillips
ncrs:2AaawqgIu1edA:Dick Snow
nkw:UJ5TNpOBjOIkg:Ken Wright
nbnr:ZFzRNtiqA.HXE:Nick Rossiter
nmrm:jAIqtDEolVKxY:Martin McLauchlan
namk:MYp383eEKVBQI:Albert Koelmans
nlfm:n3CcSAUEnkt/Q:Lindsay Marshall
npde:XywybIkyCZfDU:Paul Ezhilchelvan
nnas:JAnkXNWjFRmV2:Neil Speirs
ncmh:LDJXyq4LvdXjA:Chris Holt
njsf:fxbrIoGv8skMY:John Fitzgerald
nljs:yPBPydZVb2oV.:Jason Steggles
ngm:Eup9.OnZ04AsM:Graham Morgan
nsr:RYxOLUe9WjyZU:Steve Riddle
nnfh:ngowr/aPxnqI6:Nigel Hall
ngmt:B0E/VlmjOvSbo:Gerry Tomlinson
ncrr:urUg1XGMqAvuY:Chris Ritson
njkw:ocKDxwrevSQqw:Jim Wight
ndiw:0bfwV7bYHkCu6:Iain Wood
namb:H9v93uDQFy10g:Alex Barfield
njhw:ChNBCoq/AUsuo:Jon Warwick
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Super strong crypto
Date: Mon, 26 Feb 2001 17:36:15 GMT
Bryan Olson wrote:
> As I wrote, I think David Wagner had a point that you didn't
> really get.
If you mean, that entropy couldn't be introduced fast enough
without using up the bandwidth for overhead, that was mistaken
and corrected in a later post.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: "RSA vs. One-time-pad" or "the perfect enryption"
Date: Mon, 26 Feb 2001 17:37:43 GMT
William Hugh Murray wrote:
> Modern cryptography is not provable or perfect. However, it is
> demonstrably, as opposed to provably, good enough, as opposed to
> perfect.
I would like to see such a demonstration. What threat model
are you assuming, against high school hackers?
------------------------------
From: Volker Hetzer <[EMAIL PROTECTED]>
Subject: Re: Help Please !!!!!!!!!!!!
Date: Mon, 26 Feb 2001 18:50:42 +0100
PADDOCK wrote:
>
> the following is a list of unix crypt passwords
>
> have broken 15 of them using John the ripper and crack etc
> but can't get the rest - any ideas u clever bods?
>
> (and no, this is not for anything illegal!)
Then, what *is* it for?
Volker
--
They laughed at Galileo. They laughed at Copernicus. They laughed at
Columbus. But remember, they also laughed at Bozo the Clown.
------------------------------
From: Darren New <[EMAIL PROTECTED]>
Subject: Re: The Key Vanishes (fwd)
Date: Mon, 26 Feb 2001 17:41:36 GMT
Mok-Kong Shen wrote:
> OR the bulk encryption cipher. In this case, it is PROVABLE
> they can do nothing provided only they have less than, say,
> 100 billion GB of storage.
If they manage to be able to record (say) 1/2^256 worth of the random bit
stream, isn't it possible that they just happened to guess the right set of
bits to record? This differs from the OTP in the sense that they can't prove
they got the right decoding with the OTP. But in the exceedingly small
probability that the bad guys did indeed record the right set of bits, they
would know it. Just like in the exceedingly small probability that they
guess the right key to use with AES on the first try, they know it.
Admittedly, if they didn't guess the right bits to record, they would know
that too.
Maybe someone can clarify just what it is that the proof was supposed to
prove?
--
Darren New / Senior MTS & Free Radical / Invisible Worlds Inc.
San Diego, CA, USA (PST). Cryptokeys on demand.
"San Diego already has the hilltop villages.
We're just missing the midieval towers."
------------------------------
** 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
******************************
