Cryptography-Digest Digest #34, Volume #11 Tue, 1 Feb 00 23:13:02 EST
Contents:
Re: NIST, AES at RSA conference ("Joseph Ashwood")
Re: KEA gains something with RSA instead of D-H (David Hopwood)
OT: Reducing swap file use in Windows 98 ("cedric frost")
Re: How to Annoy the NSA ([EMAIL PROTECTED])
Re: Private-key RSA (John Savard)
Re: Private-key RSA (John Savard)
Re: Does the NSA have ALL Possible PGP keys? (Jerry Coffin)
Re: How to Annoy the NSA (Greg)
Re: How to Annoy the NSA (Jerry Coffin)
Re: Sbox construction idea (Tim Tyler)
----------------------------------------------------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: NIST, AES at RSA conference
Date: Tue, 1 Feb 2000 17:26:06 -0000
> Well, there was a security proof against differential-like
attacks
> against 6+epsilon rounds (epsilon is usually 2 if we think
about
> 2R attacks).
>
> The flaw which was discovered was a differential attack
against one
> round.
The problem is in getting that many rounds, in my original
proposal it can only be achieved by converting the base
between rounds (a rather expensive operation, a simple
choice of using more or fewer bits won't work). No matter
how many rounds are applied it is equivalent to another key
used in a single round. If a perfect generator is used for
the round keys, then it can be reduced to a single round of
my original proposal. Even changing the number of bits per
sub-block is of no use because an ordering of k bit
subblocks can be expressed as an ordering of bits (a
sentence is an ordering of words can also be considered an
ordering of letters). It is based on this that I feel
confident in stating that regardless of the number of rounds
used it is equivalent to 1 round, and so the proof against
differential attacks does not apply.
This flaw is fatal to the security of the system I proposed,
unless there is an addition of another type of round
function, which is a different matter, this would also
change the makeup of the proof and I admit may be
significantly secure. My basic point remains, that even a
proof of difficulty of a certain (fundamental) part of the
cipher being extremely hard does not prove that the cipher
is at all strong.
Joe
------------------------------
Date: Wed, 02 Feb 2000 01:19:25 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: KEA gains something with RSA instead of D-H
=====BEGIN PGP SIGNED MESSAGE=====
John Savard wrote:
>
> The Diffie-Hellman key exchange method involves one party knowing x,
> the other knowing y, A^x and A^y (mod p) being public, and only the
> two parties can determine A^(xy) (mod p). Note that knowing either
> party's private key is sufficient to derive A^(xy) from A^x and A^y.
Normally, DH is not used with fixed public values for each side. In fact
that is one of its main strengths: because key pair generation is very
fast (one modular exponentiation), ephemeral keys can be used for each
session.
Plain DH does not provide any protection against a man-in-the-middle
attack, so it is very often modified to add authentication. For example,
signing the exponentials with long-term signature keys gives the
Station-To-Station protocol. For STS, knowing even both of the long-term
keys does not allow a passive attack. Knowing a user's long-term key
allows impersonating a user, and knowing both long-term keys allows
a man-in-the-middle attack. (Techniques such as key update, variants of
the interlock protocol, and use of strong password authentication, can
make it more difficult to exploit this, but can't prevent it completely.)
Using ephemeral keys is much less practical for RSA, because RSA key pair
generation requires finding two large primes, which for secure key sizes
is *much* slower than a modexp. (The "DHE_*" ciphersuites in SSL provide
perfect forward secrecy and resistance to known-key passive attacks,
for example, whereas the RSA-based ciphersuites do not.)
> RSA, on the other hand, involves the exchange of messages which, while
> they were composed by the originator, can only be read with the
> private key of one of the parties.
>
> Hence, if a protocol like KEA were used, sending two session keys in
> opposite directions simultaneously, but with RSA instead of
> Diffie-Hellman, with the XOR of the two session keys being used as the
> actual session key, communications would remain secure *even if the
> private key of one party had been compromised*.
I don't see how KEA [KEA] can be adapted to use RSA without completely
redesigning it, but maybe I'm missing something. Standard KEA (the
key agreement protocol, rather than the email variant) is this:
Alice and Bob agree on parameters g, p, and q
(q is the order of g in GF(p)).
Alice has private key xA, public key YA = g^xA.
Bob has private key xB, public key YB = g^xB.
Alice and Bob are assumed to know each other's authentic public key.
(Key validation: check that YA and YB are elements of the order-q subgroup)
Alice: RA = g^rA mod p (rA is chosen randomly).
Bob: RB = g^rB mod p (rB is chosen randomly).
Alice -> Bob: RA
Bob -> Alice: RB
Alice & Bob check that RA and RB are elements of the order-q subgroup.
Alice: tAB = YB^rA mod p
Bob: tBA = YA^rB mod p
Alice: uAB = RB^xA mod p
Bob: uBA = RA^xB mod p
Alice: w = (tAB + uAB) mod p
Bob: w = (tBA + uBA) mod p
Alice & Bob check that w != 0, and derive a key from it (details omitted)
This is quite similar to some of the MTI* protocols, for example
MTI/A0 [HAC Protocol 12.53] and MTI/C1. It's also similar to a protocol
I designed myself (unpublished, called SID-3-DH), in which the agreed
value is g^((xA + rA)(xB + rB)), rather than g^(xB.rA) + g^(xA.rB).
[This is more efficient than KEA, because
g^((xA + rA)(xB + rB)) = (YB * RB)^(xA + rA)
= (YA * RA)^(xB + rB)
can be calculated by each side using only one modexp, not two. Like KEA,
a prime-order subgroup can be used with the exponents taken mod q. Some
additional checks and constraints on the parameters are needed, though.
It can be proven that calculating the agreed value from the information
available to the attacker reduces to DHP, for various reasonable attack
models. I will publish this protocol at some point, but I've been busy
with other things recently.]
How were you intending to adapt KEA to use RSA?
> (There is, however, no inherent immunity to the man-in-the-middle attack.
> But if one party has access to a better key certificate database - or
> more secure access to the certificate database - than the other, then
> KEA with D-H will also help avoid that attack. Perhaps that is its
> point.)
Yes, but STS, MQV, and most other authenticated variants of DH that I'm
aware of also have this property.
[HAC] A. Menezes, P.C. van Oorschot, S.A. Vanstone,
Handbook of Applied Cryptography, CRC Press, 1997.
http://www.cacr.math.uwaterloo.ca/hac/
[KEA] NIST,
"SKIPJACK and KEA Algorithm Specifications,"
Version 2.0, 29 May 1998 (published 24 June 1998).
http://csrc.nist.gov/encryption/skipjack-kea.htm
http://jya.com/skipjack-spec.htm (HTML version)
- --
David Hopwood <[EMAIL PROTECTED]>
PGP public key: http://www.users.zetnet.co.uk/hopwood/public.asc
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
"Attempts to control the use of encryption technology are wrong in principle,
unworkable in practice, and damaging to the long-term economic value of the
information networks." -- UK Labour Party pre-election policy document
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOJdwyDkCAxeYt5gVAQG9yQgAlDFAV6K4aXthtfycQvGOL1w9i6nNuTEm
BCphzkRViBE5SCnfqEyBZHNLa2M3KIygHJgXZSVwvrgQ0ZftEU0oG/vPmEOwPon6
2yEYNEcUZqg8lKNSzXagjzlrUibxawMFkkzoPC1oQtRbqW0wrWbmHB8H2EwN1tuk
XfHkpzqlJL8OEex0c0FHqAFAXG6FHEyD3qlJS6tXyoZjsy/fesyieeeLYvWtEU2P
CK/W2aeOtAEGyERB/Db0zS05OSJhB1O7iKA5BNmhL/UN55U9QPYBjzCldkpxIOb6
OGBN45TkkKm2pOgP81zrAq9i7TNAjNzq656PskWomUsjpH9dvWyDgw==
=jFDy
=====END PGP SIGNATURE=====
------------------------------
From: "cedric frost" <[EMAIL PROTECTED]>
Subject: OT: Reducing swap file use in Windows 98
Date: Tue, 1 Feb 2000 20:41:20 -0500
I found this tip for reducing Windows' dependency on the swap file directed
at those wishing to improve system performance, but I thought it would be
worth mentioning here since it can potentially reduce the risk of Windows
swapping keys, plaintext or other sensitive data out to disk.
"Windows 98 added a new feature, PageFile_Call_Async_Manager, that allows
the Memory Manager to asynchronously write out page file (swap file) buffers
during periods of time when VFAT file system activity is not busy...
You can disable this feature, causing the system to behave as Windows 95
does, at some cost in overall system performance. Add the following entry to
the System.ini file under its [386Enh] section:
[386Enh]
ConservativeSwapfileUsage=1
"
The original text is at http://m1.aol.com/axcel216/98-4.htm
Cedric
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: How to Annoy the NSA
Date: Wed, 02 Feb 2000 01:35:43 GMT
In article <
[EMAIL PROTECTED]
ing.com>,
Jerry Coffin <[EMAIL PROTECTED]> wrote:
> In article <8778es$r8d$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
> says...
>
> [ ... ]
>
> > You are wrong again. According to Science
> > Magazine (vol. 275, page 1570, March 14,
> > 1997) "hard" problems, or NP-Complete
> > problems "underlie nearly all cryptography and
> > computer security codes".
>
> You're getting things backwards: when Science Magazine publishes an
> article the contradicts Doug Gwyn (among others) about cryptography,
> it isn't _quite_ proof that the article you've read is wrong, but
> there's a LOT better chance that the article is wrong (or
> oversimplifying) than that he is.
>
> > If you don't believe
> > me then check out links like the RSAsecurity
> > link in my previous message and
> > www.cs.ccu.edu.tw/~ccc/student/dcl/dcl.htm
> > Despite the issue of NP-completeness, such a
> > quantum computer would have awesome power
> > for factoring.
>
> A quantum computer could factor quite a bit faster than a traditional
> computer, but keep in mind that much more complete and accurate
> descriptions are available than simply "awesome power". As a matter
> of fact, we already know _exactly_ how factoring can be done on a
> quantum computer and can simulate it on a conventional computer. We
> can figure out the number of steps involved in such a process.
> Equipped with that, we can figure out exactly how large of a key is
> needed with RSA (for one example) to completely thwart the attack well
> before it exists.
>
> > Everyone should know that Al Gore did not
> > invent the internet and that it was first
> > developed as a military project about 30 years
> > ago.
>
> As usual, you're getting things just about exactly backwards. ARPAnet
> was developed in the civilian sector as a way of helping communication
> between various places (mostly colleges and universities) doing
> research sponsored by the military. The funding (or part of it
> anyway) was provided by the military, but the technology was developed
> by the civil sector. The military provided some of the big servers in
> the early days of the Internet, but most of them were simply old
> computers that weren't being used for much else -- computers in active
> military use containing anything like classified information aren't
> allowed to be connected to the Internet at all.
>
> --
> Later,
> Jerry.
>
> The universe is a figment of its own imagination.
We can lengthen the codes of RSA but this
does not alleviate their fundamental
weakness- which is that it is not possible to
show how mathematically safe they are. This
is why there is research into RSA variants,
quantum encryption, etc. ARPAnet was
initiated by the Command & Control Research
division of ARPA (started as part of the DOD
in reaction to the launch of Sputnik in 1957).
Of course the technology was developed by
civilians- just like the Manhattan Project and
almost all other DOD initiated tech projects.
In general, all public key cryptosystems are
based on "hard" problems, or NP problems (this
is also stated at the RSASecurity link I gave
before).
>
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Private-key RSA
Date: Wed, 02 Feb 2000 01:32:43 GMT
On 1 Feb 2000 14:30:21 GMT, David A Molnar <[EMAIL PROTECTED]>
wrote, in part:
>So he knows that C = K_1(P) OR C = K_2(P) .
>Now he must tell which one.
>We might say that a cryptosystem is "recipient-hiding" if the probability
>of the adversary for successfully distinguishing K_1(P) from K_2(P) in
>polynomial time is negligible.
My guess as to how a scheme like that could be achieved would be the
use of a lot of salt - the salt itself having to be encrypted. And,
since M is hard to hide, but p can be shared by many users, I suspect
that it would be easier to base such a scheme on Diffie-Hellman than
on RSA.
Send to someone whose public key is A^x a copy of A^y, and encrypt
using A^(xy) a message consisting of 160 random bits, followed by the
message encrypted first with those 160 bits as the key, and then by
A^(xy)...that should meet your requirements, as it will be quite hard
to determine the message isn't for the person whose public key is A^z.
But A and p must be shared.
John Savard (teneerf <-)
http://www.ecn.ab.ca/~jsavard/index.html
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Private-key RSA
Date: Wed, 02 Feb 2000 01:35:41 GMT
On Tue, 01 Feb 2000 19:59:23 GMT, [EMAIL PROTECTED] wrote, in part:
>In article <876qlt$b8n$[EMAIL PROTECTED]>,
> David A Molnar <[EMAIL PROTECTED]> wrote:
>> > Maybe even if he has a quantum computer (as there are an infinite
>> > number of Public(so-called)-keys)?
>> No, there is a finite number of public keys. About phi(n) of them,
>> actually. No idea how that helps/hurts a quantum computer
>Sorry...are you saying that there is a finite number of primes...I
>always thought there was an infinite number of primes...all these
>years...
Well, there are a finite number of primes shorter than n digits for
any n, and in practice one can choose an n such that employing numbers
bigger than that would be impossible in practice. (But this point
should have been noted, since, as you correctly point out, the number
of integers which meet the mathematical, if not the practical,
criteria for use as public keys is usually infinite, at least with
those systems I've heard of.)
John Savard (teneerf <-)
http://www.ecn.ab.ca/~jsavard/index.html
------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Crossposted-To: comp.security.pgp,misc.survivalism
Subject: Re: Does the NSA have ALL Possible PGP keys?
Date: Tue, 1 Feb 2000 19:10:57 -0700
In article
<[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
[ ... ]
> Note that we're concerned about "probably prime" numbers. It is quite a bit
> easier to test a number to see whether it is "probably prime" than it is to
> attempt every possible factorization of a number and thus PROVE that it's
> prime. Otherwise PGP never WOULD be able to generate a key.
It's entirely possible to absolutely, positively prove that a number
is prime without trying all prime factorizations of the number. Most
people generating keys for RSA don't normally use these methods, but
they definitely exist.
> Remember, a network of rather modestly-powered personal computers in the
> Netherlands broke 512-bit RSA encryption in a matter of weeks. 512-bit
> encryption, at least, seems well within the reach of pre-computing all
> possible PGP keys. It's estimated that there's approximately 2^86 of them,
> 77,371,252,455,336,267,181,195,264, though, so storing them would be a slight
> problem (we're talking about 77 billion times more storage than the biggest
> data warehouse that I've ever encountered!).
Breaking RSA of a given size is NOT normally done by generating all
possible primes of the size necessary to create the public key. Far
from it...
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: Greg <[EMAIL PROTECTED]>
Subject: Re: How to Annoy the NSA
Date: Wed, 02 Feb 2000 02:24:28 GMT
> To annoy the NSA...
Why would you want to do that for?
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Subject: Re: How to Annoy the NSA
Date: Tue, 1 Feb 2000 19:31:13 -0700
In article <8781lf$esf$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
says...
[ ... ]
> We can lengthen the codes of RSA but this
> does not alleviate their fundamental
> weakness- which is that it is not possible to
> show how mathematically safe they are.
You seem to have lost any connection to your original statements. If
you'll recall, you were talking about quantum computing breaking
nearly all current ciphers. Quantum computing has nothing to do with
this at all...
> This is why there is research into RSA variants,
> quantum encryption, etc.
I suspect that most people who've done research into forms of PK
cryptography do it for reasons completely unrelated to quantum
computing. Some doubtless do it simply because it's what interests
them. Others object to using a patented algorithm. Still others want
things like smaller keys. I've read a number of papers on methods of
PK cryptography, and seen all sorts of reasons advanced for doing
research into new systems, but not ONE of them has given quantum
computing (or even hinted in that direction) as a reason for doing
research into new algorithms.
Quantum encryption is something else entirely, and has essentially
nothing at all to do with the subject at hand.
> In general, all public key cryptosystems are
> based on "hard" problems, or NP problems (this
> is also stated at the RSASecurity link I gave
> before).
Well, at least now you're starting to speak about things in something
approaching a realistic fashion: it MIGHT be possible to use a quantum
computer to other PK algorithms than RSA. In fact, it can probably be
used to attack DH, though I haven't tried to verify this. That,
however, leaves a LOT of forms of cryptography for which it provides
absolutely NO use whatsoever -- your normal run-of-the-mill symmetric
block cipher is no more affected by the speed of a quantum computer
than it is by the speed of a jet airplane. It's barely possible that
some of the (mostly speculative) attacks involving pre-computing keys
and looking them up could be improved a bit by the database lookup
algorithms you can implement on a quantum computer, but I'm not at all
sure this would be at all useful, and in any case most of them require
more storage than exists in any case...
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Sbox construction idea
Reply-To: [EMAIL PROTECTED]
Date: Wed, 2 Feb 2000 02:47:19 GMT
Mike Rosing <[EMAIL PROTECTED]> wrote:
: Tim Tyler wrote:
:> Tom St Denis <[EMAIL PROTECTED]> wrote:
:> : In safer they use 45^x mod 257 for the sbox in the cipher
[snip idea about combining s-boxes with different moduli]
:> : Has that idea ever been discussed before? [...]
:>
:> I don't know. Would anyone care to offer me some sort of literature
:> reference that offers reasons why using a^x mod p is of interest as a
:> method of generating s-boxes?
: Yes, it's in the literature. [...]
I guess - strictly speaking - that's a reference to the literature ;-))
: These are linear sbox's, and therefore won't work for crypto.
I'm obviously lost. 45^x mod 257 is linear in some sense...?
: If you use a formula, it has to be nonlinear.
Indeed. The resulting s-box has to be non-linear to be much use.
:> I'm interested in the general question of how best to combine small
:> s-boxes to form larger s-boxes - with "security" and compactness of
:> hardware implementation being the criteria I'm most interested in.
:>
:> A key question appears to be "what is the best size of s-box to use?"
: That depends on the application! [...]
I suppose so. It depends on what sort of "strength" vs "space and speed"
trade offs you want to make, for one thing.
Most of the literature I've seen seems to discuss much larger s-boxes
than I'm thinking about.
It seems to be the (correct) popular idea that - if you make s-boxes large
enough you don't have to worry about their linearity any more - at work.
Only a relatively small number of papers seem to discuss building large
s-boxes out of lots of relatively small ones.
The smallest s-boxes I've seen used are 4x4 ones. It appears to me that
even smaller (i.e. 3x3) non-linear s-boxes could be profitably employed as
"atomic building blocks" of larger s-boxes.
It's possible that making them smaller beyond a certain point loses its
attractiveness in terms of faster operation and more iterations - but I
doubt it.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
I just took an IQ test. The results were negative.
------------------------------
** 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
******************************
