Cryptography-Digest Digest #594, Volume #13 Tue, 30 Jan 01 23:13:01 EST
Contents:
Re: Ciphertext Stealing question (Jerry Maple)
Re: A Password Protocol (John Savard)
Re: fast signing ("Joseph Ashwood")
Free Encryption Software ("George Peters")
Re: MIKE - alternative to SPEKE and PAK ("Michael Scott")
Algorithm M question (Benjamin Goldberg)
AES and randomness (JCA)
Re: fast signing (Paul Rubin)
Re: Algorithm M question (John Savard)
Re: Very short redundant serial number (Darren New)
Re: fast signing (Bob Silverman)
Re: AES and randomness (Splaat23)
Re: fast signing ("Joseph Ashwood")
Re: fast signing (Splaat23)
Re: Free Encryption Software (Splaat23)
Re: fast signing (Paul Rubin)
Re: MIKE - alternative to SPEKE and PAK (Thomas Wu)
Re: Algorithm M question (Terry Ritter)
Re: Ciphertext Stealing question (Benjamin Goldberg)
Re: AES and randomness ("Scott Fluhrer")
Re: Ciphertext Stealing question ("Scott Fluhrer")
Re: Algorithm M question (Benjamin Goldberg)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Jerry Maple)
Subject: Re: Ciphertext Stealing question
Date: 30 Jan 2001 22:51:47 GMT
Jim Gillogly <[EMAIL PROTECTED]> wrote in <[EMAIL PROTECTED]>:
>I know there are a lot of assumptions there, and as Samuel L. Jackson's
>character said in "The Long Kiss Goodnight", when you make an assumption
>you make an ass out of u and mption.
I'm a long-time lurker, this quote brought me out of the shadows.
Paraphrase of one of my favorite quotes. I believe Benny Hill predates
this - his German professor character, as he stands at the chalkboard
writing:
"When you _assume_, you make an _ass_ out of _u_ and _me_!"
Jerry
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: A Password Protocol
Date: Tue, 30 Jan 2001 22:47:56 GMT
On Tue, 30 Jan 2001 21:45:36 +0000, David Hopwood
<[EMAIL PROTECTED]> wrote, in part:
>For each guessed password, an attacker can repeat these steps (using
>an eavesdropped challenge vector), until the transmitted hash matches.
>Therefore the protocol is vulnerable to off-line password guessing
>attacks.
As noted, I was aware of this, and did not attempt to address this
particular attack here.
Earlier, I had been thinking of a protocol with this type of security,
making use of EKE techniques, but it had the flaw that the connection
between the host and the machine I call the 'security computer' had to
be relied upon. So I was thinking in the other direction here.
I will shortly sit down and think if the kind of technique I'm looking
at here can be combined with ways to avoid reliance on the user's
(likely guessable) password.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: fast signing
Date: Tue, 30 Jan 2001 15:18:06 -0800
"Paul Rubin" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> "Joseph Ashwood" <[EMAIL PROTECTED]> writes:
> > Ok to clarify:
> > I need signing to by excessively fast. I've got an application where one
> > person here expects in the 10,000 signature/second range (I doubt he'll
get
> > that speed out of his code, but that's another issue), on a
single-processor
> > x86 P4 1.5 GHz, gobs of RAM, etc.
>
> There's no way to do that many sigs/sec on that hardware on a
> continuous basis with any public key algorithm that I know of.
Yeah I'm very familiar with the problem. I've even looked at using MACs but
can't find one that fits into the threat model correctly.
> The
> way to secure audit logs is with hash chains, not public key
> signatures. See:
Unfortunately hash chains are simply not strong enough in the model I have
to work with, they have a tendancy where if one breaks, all future ones are
broken and that is unacceptable. Additionally the quoted paper is of even
less use in this case because it is a requirement that the admin be able to
read the audit log with a text editor. Not my rules, just the rules I have
to work in. Additionally you may want to look at the last sentence of that
paper, it might dissuade you from looking at it in the same light, a quick
hint it includes the words "patent pending". I am however examining
alternatives, trying to build something security-equivalent (or superior)
without it being patent-equivalent, but that's a different project.
> You might be able to do a DSA signature in 0.1 msec (1/10,000 sec) on
> that P4 with several msec of precomputation per signature, i.e. if
> you're going to have 10,000 documents to sign tomorrow, you could
> spend several hours doing precomputation today and then do all 10,000
> signatures in 1 sec, but I don't know if that helps you.
Honestly, I wish it did. I'd been thinking along the same lines, but the
usage model right now dictates, 100K/sec sustained for long periods of time.
I almost laughed at the guy when he said that. I've seen addition not be
doable at 100k/sec for extended periods of time. My next option would be a
chain of precomputes that is generated by a low-priority thread, but I doubt
even then I could get 0.1msec per signature. Honestly I think the bottleneck
is gonna be the lan for this, I figure it's not gonna be faster than 100
Mbs, giving him only 1000 bits to do his collection and serving, and when
was the last time you saw a 1000 bit webpage? This message alone is several
times that.
So much for hoping I missed something. I just wanted to make sure I couldn't
find anything faster than DSA. Well maybe in time someone will find one.
I just recieved Silverman's message, and I'll address that at the same time.
Basically I need a signing algorithm with resistance to attack of at least
DSA with 512-bit p, preferably better. If you need more information it's
basically 512-bit Discrete Log Problem, or breaking SHA-1.
Joe
------------------------------
From: "George Peters" <[EMAIL PROTECTED]>
Subject: Free Encryption Software
Date: Tue, 30 Jan 2001 18:00:59 -0600
Greetings,
An entire suite of encryption applications are available at
http://www.endecs.com/uenigma.zip . It contains two file systems, client
internet email, ftp and point to point communications and some source code.
Well worth the download.
GP
------------------------------
From: "Michael Scott" <[EMAIL PROTECTED]>
Subject: Re: MIKE - alternative to SPEKE and PAK
Date: Wed, 31 Jan 2001 00:35:37 GMT
"Michael Scott" <[EMAIL PROTECTED]> wrote in message
news:4vDd6.85753$[EMAIL PROTECTED]...
>
> "Thomas Wu" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > "Michael Scott" <[EMAIL PROTECTED]> writes:
> >
> > > "Thomas Wu" <[EMAIL PROTECTED]> wrote in message
> > > news:[EMAIL PROTECTED]...
> > > > "Michael Scott" <[EMAIL PROTECTED]> writes:
> > I thought of that too, but I noticed that Carol's computation of A
> > requires her to know 4^x, not x, so that if an impostor Chris stole
> > v=4^x from Steve, she could compute A=3^a*v mod p and Steve would be
> > none the wiser. Comments?
> >
>
Actually not so easily fixed. Steve hasn't committed to his knowledge of v
early enough, which allows an off-line dictionary attack as outlined in Wu,
section 3.2.3, so....
3. Carol: A=3^a.4^x mod p Carol sends A to Steve
4. Steve: B=v.3^b. u=4^r. Steve sends B and u to Carol.
5. Carol calculates S=(B/4^x)^a.u^x. Steve calculates S=(A/v)^b.v^r
Mike Scott
>
> >
> > Tom
> > --
> > Tom Wu * finger -l [EMAIL PROTECTED] for PGP
> key *
> > E-mail: [EMAIL PROTECTED] "Those who would give up their
freedoms
> in
> > Phone: (650) 723-1565 exchange for security deserve
> neither."
> > http://www-cs-students.stanford.edu/~tjw/
> http://srp.stanford.edu/srp/
>
>
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Algorithm M question
Date: Wed, 31 Jan 2001 00:41:30 GMT
Does anyone know of any place where Knuth's Alogithm M is actually used?
For those who don't recall what it is offhand, here's a sample version:
unsigned long delay[256];
unsigned long algorithmM() {
unsigned long a, b;
a = prngA(); a ^= a >> 16; a ^= a >> 8;
b = delay[a&0xFF]; delay[a&0xFF] = prngB();
return b;
}
Of course, the delay[] array must first be filled using prngB, but this
is minor. A fast, statistically good generator, like MT, might be
usable for both PRNGs -- provided of course, that MT with scrambled
order outputs is secure.
--
Most scientific innovations do not begin with "Eureka!" They begin with
"That's odd. I wonder why that happened?"
------------------------------
From: JCA <[EMAIL PROTECTED]>
Subject: AES and randomness
Date: Tue, 30 Jan 2001 16:23:25 -0800
I wonder if there are any results about Rijndael as a
PRNG. Anybody?
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: fast signing
Date: 30 Jan 2001 17:15:48 -0800
"Joseph Ashwood" <[EMAIL PROTECTED]> writes:
It would help if you could say what the application is. What is being
signed? Web pages? From a web server? You're trying to prove at the
server side that the client actually received the data you said you
sent? I don't think you'll ever make that fly.
Anyway, look into secret-key MAC's generated by a sealed hardware module,
that can sign and verify but won't reveal the keys.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Algorithm M question
Date: Wed, 31 Jan 2001 01:10:13 GMT
On Wed, 31 Jan 2001 00:41:30 GMT, Benjamin Goldberg
<[EMAIL PROTECTED]> wrote, in part:
>A fast, statistically good generator, like MT, might be
>usable for both PRNGs -- provided of course, that MT with scrambled
>order outputs is secure.
The MacLaren-Marsaglia generator, if used with 'conventional' insecure
PRNGs, is not generally believed to be secure. I think it's not that
bad, as long as you restrict the output to the most significant few
bits of the PRNG output, however.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Darren New <[EMAIL PROTECTED]>
Subject: Re: Very short redundant serial number
Date: Wed, 31 Jan 2001 01:23:23 GMT
> I know this is borderline faq, but hopefully one of you can help me
> out. I need to create a very short list of serial numbers, only 100.
> Users will be entering in the number manually on a keypad. I would
> like to build in some redundancy so they have a lower chance of
> accidently entering the wrong number. Say 2 more digits (4 total).
Why not just make a list of 00 thru 99, then add two more digits that are
different for each pair, and store the whole list?
1700
5801
3502
8603
...
Maybe I'm missing something, but I'm not sure why it needs a "scheme" at
all. Once you have the list, it should be easy to check that
off-by-one-digit errors aren't too close together, etc.
--
Darren New / Senior MTS & Free Radical / Invisible Worlds Inc.
San Diego, CA, USA (PST). Cryptokeys on demand.
"It says this wine has syphilis."
"I think that's pronounced `sulphates'."
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: fast signing
Date: Wed, 31 Jan 2001 02:14:58 GMT
In article <[EMAIL PROTECTED]>,
Paul Rubin <[EMAIL PROTECTED]> wrote:
> Bob Silverman <[EMAIL PROTECTED]> writes:
> > I'm just making his suggestion public. I've let e be large.
> > We get d = 3 and now signing is very fast and verification slow,
> > instead of the other way around....
>
> Um, now that the signing exponent is known, the signatures don't
> authenticate much any more...
Sure. But how is it known? All you do is publish e. How
does someone else know then that d = 3? phi(n) is still unknown,
so there is no way to compute d from e....
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Splaat23 <[EMAIL PROTECTED]>
Subject: Re: AES and randomness
Date: Wed, 31 Jan 2001 02:11:04 GMT
I would venture to say that any one of of the AES finalists can be used
as the symmetric block cipher in a PRNG that uses one, such as Yarrow.
- Andrew
In article <[EMAIL PROTECTED]>,
JCA <[EMAIL PROTECTED]> wrote:
>
> I wonder if there are any results about Rijndael as a
> PRNG. Anybody?
>
>
Sent via Deja.com
http://www.deja.com/
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: fast signing
Date: Tue, 30 Jan 2001 18:10:28 -0800
"Paul Rubin" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> What is being
> signed? Web pages? From a web server?
Just signing the audit log, everytime an audited page access is attempted an
audit entry is generated, and every so often it is signed (default 16
entries). It's basically so the admin can do post-mortem analysis.
> Anyway, look into secret-key MAC's generated by a sealed hardware module,
> that can sign and verify but won't reveal the keys.
It seems like we all agree on the various things, the MAC idea was
considered, but they (as in my boss) want the audit log verifiable without
being able to forge (sometimes paranoia runs deep). I'm looking to various
hardware solutions. I personally don't think speed-wise it's worth it (most
aren't that much faster, the bottleneck is the connection), but I do like
the security benefits. Anyway, I guess I'll just have to go forward with the
DSA signing, maybe sometime in the future something faster will be
available.
Joe
------------------------------
From: Splaat23 <[EMAIL PROTECTED]>
Subject: Re: fast signing
Date: Wed, 31 Jan 2001 02:27:56 GMT
It's known because the system is known (assuming public knowledge of
the mechanics) and the attacker can can do a quick run through d = 3,
17, 257, 63357, 5, ... for the best (fastest) d's. Low private exponent
= bad!
- Andrew
In article <957ses$9jg$[EMAIL PROTECTED]>,
Bob Silverman <[EMAIL PROTECTED]> wrote:
> In article <[EMAIL PROTECTED]>,
> Paul Rubin <[EMAIL PROTECTED]> wrote:
> > Bob Silverman <[EMAIL PROTECTED]> writes:
> > > I'm just making his suggestion public. I've let e be large.
> > > We get d = 3 and now signing is very fast and verification slow,
> > > instead of the other way around....
> >
> > Um, now that the signing exponent is known, the signatures don't
> > authenticate much any more...
>
> Sure. But how is it known? All you do is publish e. How
> does someone else know then that d = 3? phi(n) is still unknown,
> so there is no way to compute d from e....
>
> --
> Bob Silverman
> "You can lead a horse's ass to knowledge, but you can't make him
think"
>
> Sent via Deja.com
> http://www.deja.com/
>
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Splaat23 <[EMAIL PROTECTED]>
Subject: Re: Free Encryption Software
Date: Wed, 31 Jan 2001 02:32:55 GMT
Couldn't find any concise description of the algorithms used, so I
deleted it. That .zip file has ~1000 files, a little much for me to
wade through. Why is it using Enigma? Any particular reason I should
use it? I really hope this message is real and not some stupid attempt
at advertising...
- Andrew
In article <#MX$hlxiAHA.273@cpmsnbbsa07>,
"George Peters" <[EMAIL PROTECTED]> wrote:
> Greetings,
>
> An entire suite of encryption applications are available at
> http://www.endecs.com/uenigma.zip . It contains two file systems,
client
> internet email, ftp and point to point communications and some source
code.
> Well worth the download.
>
> GP
>
>
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: fast signing
Date: 30 Jan 2001 18:40:17 -0800
"Joseph Ashwood" <[EMAIL PROTECTED]> writes:
> > Anyway, look into secret-key MAC's generated by a sealed hardware module,
> > that can sign and verify but won't reveal the keys.
> It seems like we all agree on the various things, the MAC idea was
> considered, but they (as in my boss) want the audit log verifiable without
> being able to forge (sometimes paranoia runs deep). I'm looking to various
> hardware solutions. I personally don't think speed-wise it's worth it (most
> aren't that much faster, the bottleneck is the connection), but I do like
> the security benefits. Anyway, I guess I'll just have to go forward with the
> DSA signing, maybe sometime in the future something faster will be
> available.
Just program a second module to be able to verify the MAC's but not
sign new ones.
Look, what's the purpose of the signatures on the logs? To safeguard
against security breaches on the logging machine, right? Well, if the
logging machine can be breached, what makes your boss think the signing
machine can't also be breached?
Whether you use public key or secret key signing algorithms, you
should use secure hardware modules, not general purpose computers, to
do the signing, if the signatures are expected to be important for
something.
------------------------------
From: Thomas Wu <[EMAIL PROTECTED]>
Subject: Re: MIKE - alternative to SPEKE and PAK
Date: 30 Jan 2001 18:43:37 -0800
"Michael Scott" <[EMAIL PROTECTED]> writes:
>
> Actually not so easily fixed. Steve hasn't committed to his knowledge of v
> early enough, which allows an off-line dictionary attack as outlined in Wu,
> section 3.2.3, so....
>
> 3. Carol: A=3^a.4^x mod p Carol sends A to Steve
> 4. Steve: B=v.3^b. u=4^r. Steve sends B and u to Carol.
> 5. Carol calculates S=(B/4^x)^a.u^x. Steve calculates S=(A/v)^b.v^r
But this is precisely Jablon's B- extension for converting a non-verifier
based protocol into a verifier-based one; that's covered by his 1997 WETICE
paper. If the server knows g^x and the client knows x, the server sends
g^z (random z) and incorporates g^(zx) into the session key. The server
can compute v^z, but the client is forced to compute (g^z)^x.
Obviously, one can use the existing A- and B- methods to augment MIKE
(B-MIKE?), but that carries all the disadvantages of those extensions.
For example, I count 8 modexps in the protocol now. I'll keep looking
to see if there's a better solution for this problem.
Tom
> Mike Scott
--
Tom Wu * finger -l [EMAIL PROTECTED] for PGP key *
E-mail: [EMAIL PROTECTED] "Those who would give up their freedoms in
Phone: (650) 723-1565 exchange for security deserve neither."
http://www-cs-students.stanford.edu/~tjw/ http://srp.stanford.edu/srp/
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Algorithm M question
Date: Wed, 31 Jan 2001 03:54:23 GMT
On Wed, 31 Jan 2001 00:41:30 GMT, in
<[EMAIL PROTECTED]>, in sci.crypt Benjamin Goldberg
<[EMAIL PROTECTED]> wrote:
>[...]
>A fast, statistically good generator, like MT, might be
>usable for both PRNGs -- provided of course, that MT with scrambled
>order outputs is secure.
http://www.io.com/~ritter/RES/COMBCORR.HTM#Retter84
http://www.io.com/~ritter/RES/COMBCORR.HTM#Retter85
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Ciphertext Stealing question
Date: Wed, 31 Jan 2001 04:02:09 GMT
N. Weicher wrote:
>
> I have Ciphertext Stealing working with odd-length messages as long as
> it is over 8 bytes in length. Is there any technique that will work
> with messages less than 8 bytes in length? Padding is not an option:
> the ciphertext must be the exact length of the plaintext.
Using a [fixed] known value as the IV, encrypt in CFB. By making the IV
known, you avoid having to send it. If you are encrypting to send over
some sort of network, you can use information about the connection as
your IV (eg, the socket number). Otherwise, simply using the value 0 as
IV will work fine.
--
Most scientific innovations do not begin with "Eureka!" They begin with
"That's odd. I wonder why that happened?"
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: AES and randomness
Date: Tue, 30 Jan 2001 19:57:19 -0800
JCA <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
> I wonder if there are any results about Rijndael as a
> PRNG. Anybody?
If Rijndael in counter mode weren't a wonderful CSPRNG (that is, given 2**64
outputs, there was a better attack than brute-forcing the key), this would
be *really* big news.
--
poncho
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Ciphertext Stealing question
Date: Tue, 30 Jan 2001 20:01:22 -0800
N. Weicher <[EMAIL PROTECTED]> wrote in message
news:ajEd6.3078$[EMAIL PROTECTED]...
> I have Ciphertext Stealing working with odd-length messages as long as it
is
> over 8 bytes in length. Is there any technique that will work with
messages
> less than 8 bytes in length? Padding is not an option: the ciphertext
must
> be the exact length of the plaintext.
>
> Thanks for any tips.
CFB mode, OFB mode or counter mode. If you want something a modified
ciphertext to decrypt to gibberish (IMHO, rather dubious as an
authentication technique), you can try CFB mode with the feedback size being
one byte or one bit.
--
poncho
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Algorithm M question
Date: Wed, 31 Jan 2001 04:08:26 GMT
John Savard wrote:
>
> On Wed, 31 Jan 2001 00:41:30 GMT, Benjamin Goldberg
> <[EMAIL PROTECTED]> wrote, in part:
>
> >A fast, statistically good generator, like MT, might be
> >usable for both PRNGs -- provided of course, that MT with scrambled
> >order outputs is secure.
>
> The MacLaren-Marsaglia generator, if used with 'conventional' insecure
> PRNGs, is not generally believed to be secure. I think it's not that
> bad, as long as you restrict the output to the most significant few
> bits of the PRNG output, however.
So if, before returning the result, I did:
b ^= b>>16; b ^= b>>8; b &= 0xFF;
It would be one secure byte?
Hmm. How does this generator compare in speed to other generators?
--
Most scientific innovations do not begin with "Eureka!" They begin with
"That's odd. I wonder why that happened?"
------------------------------
** 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
******************************
