Cryptography-Digest Digest #660, Volume #13 Thu, 8 Feb 01 20:13:01 EST
Contents:
Re: NPC (Benjamin Goldberg)
Re: Mod function (Jerry Coffin)
Q: WEP (Mok-Kong Shen)
Re: Mod function (Mok-Kong Shen)
Re: relative key strength private vs public key (Roger Schlafly)
Re: Enigma replicas ? (digiboy | marcus)
Re: File encryption with Rijndael (John Myre)
Re: relative key strength private vs public key (Steve Portly)
Re: ECDSA certs (=?ISO-8859-1?Q?Tom=E1s?= Perlines Hormann)
Re: MIKE - alternative to SPEKE and PAK ("Michael Scott")
Re: Encrypting Predictable Files [now on AONTs] ("parag")
Re: Phillo's alg is faster than index calculus ([EMAIL PROTECTED])
Re: Disk Overwriting (Kat Hopwood)
Re: Mod function (Jerry Coffin)
Re: Encrypting Predictable Files [now on AONTs] ("Joseph Ashwood")
----------------------------------------------------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: NPC
Date: Thu, 08 Feb 2001 21:15:40 GMT
Peter Shugalev wrote:
>
> I think someone tried to prove that either discrete log or factoring
> problem is NPC (not just NP). I'd like to see some results of these
> attempts.
>
> And if they are *not* NPC. Do you know any attempt to create a public
> key algorithm based on the problem that is known to be NPC?
Assuming that P!=NP, then any NP complete problem takes exponential time
in worst case. All known algorithms for doing factoring and DL take
more than polynomial time, but less than exponential time. I believe
(but am not certain) that they belong in a class (or maybe two seperate
classes) of superpolynomial hard problems, seperate from NP complete
problems.
The knapsack problem is NP complete, but the most of the PKE systems
which use it are broken due to lattice attacks (their method of
transforming a hard problem into a PKE system is flawed). The only
knapsack-like system which isn't broken by lattice attack is NTRU.
I don't know of any other NPC problems which are used as ciphers. Maybe
someone else does?
--
A solution in hand is worth two in the book.
Who cares about birds and bushes?
------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Subject: Re: Mod function
Date: Thu, 8 Feb 2001 14:17:38 -0700
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
says...
[ ... ]
> Logic doesn't get in the way of greed. You would think that
> it would similarly be impossible for anyone to patent the
> use of XOR to draw and erase a cursor in a bitmap, but
> exactly that did occur and was the source of litigation.
Like most people who mention this patent, you're _grossly_ mis-
characterizing it -- in fact, what you mention is specifically cited
in the patent as prior art. Yes, there was litigation. Yes, the
patent was upheld, and yes, that's because the patent covers things
you haven't mentioned, and nobody (before, during or since the trial)
has come up with even the slightest reason to believe that anybody
had actually come up with the patented technique before the patent
holders did. Above and beyond that, everybody I've ever met who has
actually done their homework and read the patent almost immediately
says something like "Geeze -- now that really IS cool; why didn't I
think of that?"
--
Later,
Jerry.
The Universe is a figment of its own imagination.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Q: WEP
Date: Thu, 08 Feb 2001 22:45:00 +0100
Could some knowledgeable person give a bit useful
information about the WEP (Wired Equivalent Privacy)
algorithm that is used in WLANs? I haven't heard of
it before but read today in a newspaper article that certain
security problems were found in it by scientists in
Berkeley. Thanks in advance.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Mod function
Date: Thu, 08 Feb 2001 22:52:07 +0100
Jerry Coffin wrote:
>
> [EMAIL PROTECTED] wrote:
> > Logic doesn't get in the way of greed. You would think that
> > it would similarly be impossible for anyone to patent the
> > use of XOR to draw and erase a cursor in a bitmap, but
> > exactly that did occur and was the source of litigation.
>
> Like most people who mention this patent, you're _grossly_ mis-
> characterizing it -- in fact, what you mention is specifically cited
[snip]
Is that patent available online? Could someone give the
URL? Thanks.
M. K. Shen
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: relative key strength private vs public key
Date: Thu, 08 Feb 2001 13:56:37 -0800
DJohn37050 wrote:
> NIST has agreed that the minimum DSA key size is 1024 bits. This will be made
> explicit in the update to DSA (aka DSA-2) that will allow use of longer hash
> output sizes (SHA-2).
You mean NIST intends to agree to that. AFAIK, 512-bit DSA keys
still conform to the FIPS.
------------------------------
From: digiboy | marcus <[EMAIL PROTECTED]>
Subject: Re: Enigma replicas ?
Date: Thu, 08 Feb 2001 22:02:54 GMT
In article <95u366$gmg$[EMAIL PROTECTED]>,
"*" <[EMAIL PROTECTED]> wrote:
> I was wondering if any company ever produced Enigma replicas (for us,
> crypto enthousiasts
I remember seeing replicas somewhere in print, but haven't been able to
find any through the net. Can't remember who it was making them though.
I'd be interested in gettin' one myself... or any of the original
codebooks as well...
--
[ marcus ] [ http://www.cybergoth.cjb.net ]
[ ---- http://www.ninjakitten.net/digiboy ]
Sent via Deja.com
http://www.deja.com/
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: File encryption with Rijndael
Date: Thu, 08 Feb 2001 15:23:01 -0700
Well, it's OT, as you said, but I'll respond anyway. I
am *not* trying to claim that Java class files will
run identically everywhere. Nor am I trying to claim that
Java is always, or even nearly always, the best choice.
What I *do* claim is that Java is usually easier to port,
i.e., requires less work, than porting assembler. I don't
know how one could dispute this, except to misunderstand
me to say that Java is "always" better.
Doubtless there are cases where porting assembler is the
best choice. It is my opinion that those cases are rare.
As you and others have noted, if you are in the business
of porting (not writing from scratch), C is probably the
default choice.
As far as the references I gave, I am not trying to
imply that those smartcards support "the" JVM. I was
responding specifically to your comment, where you said
that "there will never be a JVM on a chip-card". The
references are for actual smartcards on which Java is
already supported, which means there is indeed "a JVM"
on those cards, now. If you would like to amend your
prediction to say that "there will never be a full
implementation of *the* standard JVM on a chip-card"
then perhaps you have a point. But maybe not; in ten
years a "chip-card" might be pretty powerful, and Java
might have ossified into a single standard, too. I'm
not that good at predicting the future, but I'll stick
with my guess that Java on chip-cards will be a reality.
JM
------------------------------
From: Steve Portly <[EMAIL PROTECTED]>
Subject: Re: relative key strength private vs public key
Date: Thu, 08 Feb 2001 17:39:54 -0500
Roger Schlafly wrote:
> DJohn37050 wrote:
> > NIST has agreed that the minimum DSA key size is 1024 bits. This will be made
> > explicit in the update to DSA (aka DSA-2) that will allow use of longer hash
> > output sizes (SHA-2).
>
> You mean NIST intends to agree to that. AFAIK, 512-bit DSA keys
> still conform to the FIPS.
For purposes such as intellectual property protection you might have the case where
a key should last for 30 years or more. Current standards are fine for day to day
E-commerce of course. For those of you that write your own programs and generate
large prime number composites you may have noticed that the spacing between prime
numbers grows quite large. Prime numbers only occur about one in a hundred thousand
numbers at current key sizes. I am wondering if there might be some point in the
future (30 years down the road) in which prime numbers are not as an attractive
alternative for public key systems? Any math theory to prove disprove this? The
german enigma was a good wartime field cipher prior to 1940. The cipher was
designed to protect information long enough for the value of the information to
expire. I doubt the people that developed it believed it was invincible forever.
Today 60 years later a high school student running a colossus emulator can break the
code easily. Todays public key systems may prove just as easy to break in
time.
------------------------------
From: =?ISO-8859-1?Q?Tom=E1s?= Perlines Hormann <[EMAIL PROTECTED]>
Subject: Re: ECDSA certs
Date: Thu, 08 Feb 2001 23:48:12 +0100
I am interested as well in his address. As I am living in Europe, it's
kinda hard for me to attend any X9F1 meetings, specially being a
student, not an employee...
Would be nice if any of you could either send me the e-mail address of
Phil Griffin, or send me the spec directly. Thanks a lot...
Roger Schlafly wrote:
> DJohn37050 wrote:
>
>> X9.68 is in ballot, editor is Phil Griffin. To get it, you need to attend an
>> X9F1 meeting where it is on the agenda (which is open to public) or ask the
>> editor and see if you can get one for review purposes. Once it is an official
>> ANSI X9 standard, it can be purchased.
>
>
> Do you know anyone who would be willing to email me a copy? Do you
> have Phil's email address?
--
--
Quick answering: mailto:[EMAIL PROTECTED]
Check it out: http://www.weh.rwth-aachen.de/~tomas
Do it Now!
:o) Tomás Perlines (o:
------------------------------
From: "Michael Scott" <[EMAIL PROTECTED]>
Subject: Re: MIKE - alternative to SPEKE and PAK
Date: Thu, 08 Feb 2001 22:48:21 GMT
"Thomas Wu" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> "Michael Scott" <[EMAIL PROTECTED]> writes:
> >
> > Quite right. That was dumb of me. Which leaves me with either.....
> >
> > 3. Carol: A=3^a mod p, w=4^c mod p, a and c random. Sends {A,w} to Steve
> > 4. Steve: B=3^b.v^r mod p. u=4^r mod p, b and r random. F=H(w^r). Sends
> > {B,u,F} to Carol
> > 5. Carol: Check F=?=H(u^c). If not abort, else S=(B/u^x)^a. Steve
calculates
> > S=A^b
> >
> > The idea is the same, to force Steve to make u=4^something by engaging
in a
> > base-4 Diffie-Hellman. Only if it he does will Carol continue.
> >
> > ..... or the somewhat faster alternative, as previously posted but
tidied up
> > a little, which includes the result of the base-4 DH in the key.
> >
> > 3. Carol: A=3^a mod p, w=4^c mod p, a and c random. Sends {A,w} to Steve
> > 4. Steve: B=3^b.v^r mod p. u=4^r mod p, b and r random. Send {B,u} to
Carol.
> > 5. Carol: S=B^a.u^(c-ax) mod p. Steve calulates S=A^b.w^r
>
> An impostor Chris has stolen Carol's v from Steve (v=4^x) and now wishes
> to impersonate Carol.
>
> 3'. Chris: A'=3, w'=4.v mod p. Sends {A',w'} to Steve.
> 4'. Steve: B=3^b.v^r mod p, u=4^r mod p, b and r random. Sends {B,u} to
Carol.
> 5'. Chris calculates S = B.u = 3^b.v^r.4^r
> Steve calculates S = A'^b.w'^r = 3^b.(4.v)^r = 3^b.4^r.v^r
>
> This protocol can be broken by an adversary who steals v, and does not
> require a dictionary attack, since the client can log in without knowing
> the real password x. This attack generalizes easily, so it cannot be
> prevented by checking A and w for these specific values. Oddly enough,
> Chris's attack is actually more efficient than a normal protocol run(!)
>
> Frankly, I'm not sure grafting on extensions this way is the best way
> to design a secure verifier-based protocol, because it's just too easy
> to break something in the process of patching something elsewhere,
> given what's happened with these last few proposals.
>
That's very clever! I had a feeling in my bones that including the outcome
of the base-4 Diffie-Hellman multiplicatively in the key was dangerous, but
I couldn't identify a problem myself. I was seduced to suggest it by the
performance benefit. I should really come up with a basic feasible solution
first (if indeed one is possible) before trying to optimize it.
However this attack doesn't work on the first variant I suggested.
Here it is again, slightly re-organised.
Verifier v stored by Steve =4^x
3. Carol: A=3^a mod p, w=4^c mod p, a and c random. Sends {A,w} to Steve
4. Steve: B=3^b.v^r mod p. u=4^r mod p, b and r random. Sends {B,u} to Carol
5. Carol: Calculate the key as K=H((B/u^x)^a,u^c). Steve calculates
K=H(A^b,w^r)
I observe that its important a!=c otherwise Stevie sends B=4^b in step 4,
and can launch an off-line attack on x. Similarily b!=r otherwise Chris can
send A=4^a in step and then calculate Steve's key, and indeed log in as
anyone he likes. It appears that {A,w} and {B,u} can be swapped
simultaneously - the order doesn't seem to matter, so steps 3 & 4 are really
the same step.
If Carol stores a secret password from Steve as well, s=4^z, then there is a
nice symmetric protocol. Change Carol's calculation of A to A=3^a to
A=3^a.s^c. Steve's key calculation is then K=H((A/w^z),w^r). This reduces
to the protocol above by setting z=0.
The performance I admit is inferior to that of SRP, but competitive I think
with B-SPEKE. I can't see any obvious way to speed it up.
Comments?
Mike Scott
> > 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: "parag" <[EMAIL PROTECTED]>
Subject: Re: Encrypting Predictable Files [now on AONTs]
Date: Thu, 8 Feb 2001 10:52:58 -0800
<[EMAIL PROTECTED]> wrote in message news:95sulh$kqk$[EMAIL PROTECTED]...
> In article <uQfPzuVkAHA.341@cpmsnbbsa09>,
> more to it than just [D]AONT and NDAONT.
> I think many methods
> leave signatures in the result output.
[I will commonly refer to 3 text types in this message, PT, TT, and CT.
These come from Plaintext, Transform Text, and Ciphertext, and an algorithm
order of PT is plaintext, TT = AONT(PT), CT = encipher(TT, Key), reversal is
self-obvious]
Then we should start placing grades on AONTs as we have on ciphers.
Something like OAEP, would of course be given (at least close to) the
highest grade, this because with one bit encrypted it is not possible to
recover any portion of the plaintext faster than recovering that bit. Under
alternative views encrypting using DES(w/known key) with CBC can be an
AONT, encrypting the first block using the last block can be considered an
AONT, however it is not of the same grade since some of the PT can be
recovered without recovering the entire TT. This allows various grey areas
of attackability. A perfect AONT has the property that encrypting any k bits
with a k-bit cipher results in the PT being recoverable at the same rate as
breaking the encryption. There are other considerations that can be given,
such as your concept of not leaving any mathematic traces, offering a 1-1
onto mapping, or others.
It is worth noting however that different measures need to be applied to the
two different classes of AONTs. A DAONT (Deterministic AONT) would almost
out of necessity be a 1-1 onto tranform (that is F(F'(F(X))) = F(X) for all
X), while a NDAONT (Non-deterministic AONT) would out of the fact of being
non-deterministic have the property that F(F'(F(X))) =/= F(X) with high
probability for all X, however for all X there must exist a Y such that
F'(X)=Y. Whether or not X is a compressed value or not is of little
interest.
Joe
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Phillo's alg is faster than index calculus
Date: Thu, 08 Feb 2001 22:50:12 GMT
> My point is why would I make claims that I am not prepared to back up?
If I
> am not a theologian than I shouldn't stake claims.
>
> Likewise if he can't back up his algorithm with solving my system
(using
> relatively small parameters) then he shouldn't tote it as the next
mesiah.
You may have twisted my orginal post a bit.
Let me try it in a different way.
I said, "Phillo's alg is faster than index calculus...What do you
think?"
So you may answer one of the following:
a. Yes, it is because __________.
b. No, it isn't because ___________.
The answer (with the real technical reason) can be as short as 1
sentence. Now try fill in the blank.
Sent via Deja.com
http://www.deja.com/
------------------------------
Date: Thu, 08 Feb 2001 23:50:50 +0000
From: Kat Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Disk Overwriting
=====BEGIN PGP SIGNED MESSAGE=====
"Albert P. Belle Isle" wrote:
> The armed services' standards for disk data overwriting are NAVSO
> P5239-26, AFSSI-5020 and AR 380-19, respectively.
>
> All of them meet or exceed the requirements of DOD5220.22-M (the
> latest ones, not the old 3-pass "character, complement and random"),
> and all of which require READ-BACK VERIFICATION - which most
> "overwriting software" neglects - to be sure that improper
> cache-flushing leaks haven't resulted in the kind of "fast
> overwriting" that never makes it to disk (like the PGP bug).
Is there not a risk that the read-back will just read from cache,
either at the operating system or disk controller level? (I'm not
disputing that it's a good idea to do read-back verification, just
pointing out that it may not be sufficient.)
Ideally, disk controllers would have a feature that guarantees to
commit all writes to the disk surface (with a notification when that
has been completed), and operating systems would make this available
to applications. I'm not holding my breath, though.
- --
David Hopwood <[EMAIL PROTECTED]>
Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOoIsUjkCAxeYt5gVAQEflAgAv5tyEzRb5SwvW9DvLCCYJ6sXJsiyrW/L
/ooqaU28VC+ots7GrFmryLyoq1WkWr4qit0f9tZFx5Z8rbYgiZjiK+BCSAxH4xeH
lD71SlS/3vMHDG9fC+H7zEy6Br2oKvbdJppJNxLgwkVOqoGYNnno208XqJ7DSt6I
M26B4Fx8vEFHSf//4bPKp1t9Im2au6lJ6iN0l19Po7RcmQzGsSyg+YkJhxvoB84W
OAVYs99vglVTuY58vKDrcR8Ox62xZoOcPM6rJkTKNab1A4Lo0WQwUdu34pIQR0HX
u/9B/heO/shjWXSToEbMm2u8DfJw/AiXuV8gmD2z8lRuWu4jAVCKzA==
=sJcF
=====END PGP SIGNATURE=====
------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Subject: Re: Mod function
Date: Thu, 8 Feb 2001 17:28:46 -0700
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
says...
[ ... ]
> Is that patent available online? Could someone give the
> URL? Thanks.
Reasonably recent US patents are available online at
www.delphion.com. Offhand I don't have the number of the patent
being discussed though...
--
Later,
Jerry.
The Universe is a figment of its own imagination.
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Encrypting Predictable Files [now on AONTs]
Date: Thu, 8 Feb 2001 15:47:16 -0800
Oops, this is actually from me. I don't know how the e-mail address stuck
(it was for demonstration purposes).
"parag" <[EMAIL PROTECTED]> wrote in message
news:eb05bHikAHA.339@cpmsnbbsa09...
should read "Joseph Ashwood" [EMAIL PROTECTED] wrote . . . .
Joe
------------------------------
** 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
******************************
