Cryptography-Digest Digest #363, Volume #14 Wed, 16 May 01 03:13:01 EDT
Contents:
Re: DSA, ECDSA, RSA (Gary Silverman)
Re: function decomposition ("Paul Pires")
Re: best algo (Gary Silverman)
Re: What Is the Quality of Randomness? (David Hopwood)
Re: Are low exponents a problem with RSA? (David Hopwood)
Re: Key escrow based on BBS (David Hopwood)
Re: OAP-L3: "The absurd weakness." (David Hopwood)
----------------------------------------------------------------------------
From: Gary Silverman <[EMAIL PROTECTED]>
Subject: Re: DSA, ECDSA, RSA
Date: Wed, 16 May 2001 00:12:16 -0500
Thank you very much for your thorough explaination and time required to type
it all.
Anton Stiglic wrote:
> The best way to analyze such algorithms is to look at the most
> expensive operations that are used (mod exps are the most expensive,
> then comes computing inverses, one mod mul or mod addition is cheap
> and negligible compared to these other operations. Hash functions
> are also cheap and negligible compared to mod exps.).
>
> So in DSA you have a public generator g, and a public key
> y = g^s mod p, corresponding to a private key s.
> You work in the subgroup of order q of Z*_p, p and q
> are publicly known. You also have a known hash function h.
> Let us say that q is 160 bit long and that p is 1024 bits long.
> To compute a signature on a message m, you pick a random
> value k and compute A = g^k mod p,
> then set B = k^{-1}*(h(m) + sA) mod q,
> the signature is (A, B).
>
> The verification is:
> compute u = B^{-1}*h(m) mod q and v = A*B^{-1} mod q,
> then verify if A = (g^u)*(y^v).
> The verification works on legitimate signatures since
> (g^u)*(y^v) = (g^{B^{-1}*h(m)}) * ((g^s)^{A*B^{-1})
> = g^(B^{-1}(h(m) + s*A)
> = g^(k*(h(m) + sA)^{-1} * (h(m) + sA))
> = g^k = A
>
> Now, the signature requires you to pick 1 random 160 bit
> value (this can be expensive if you don't have easy access
> to randomness) and to compute 1 mod exp (g^k mod p)
> as well as 1 inverse mod q (k^{-1}), along with a multiplication
> and an addition. So if you can get randomness in an efficient
> matter, the most costly operation is the mod exp. Note
> that you your exponent is of size 160 bits, this is about
> 1024/160 ~= 6.4 times faster then if you had a 1024 bit exponent.
> Note as well that you can precompute these exponentiations
> and inverses, (but also note that I think there might be a
> patent on that).
>
> The verification involves 1 inverse mod q and 2 mod p exps
> (with 160 bit exponents).
>
> Now let's look at RSA with a N = pq, N of size 1024 bits.
> Signature on m is
> h(m)^d mod p, where d is a secret, 1024 bit exponent.
> Verification is checking if
> (h(m)^d)^e mod p == 1
> e is the verification key, it is such that e*d == 1 mod phi(n),
> you can choose the private/public key pair so that e is small,
> such as e = 3, in which case computing a^e is like computing
> a*a*a, and is negligible to a "full" mod exp and verification
> is super fast. Computing the signature is less efficient than
> for DSA, the mod exp you do is with a 1024 bit exponent.
>
> When you use elliptic curves, you usually talk in the additive
> group notation. And the expensive operation becomes multiplication
> of a point by a scalar. But a multiplication of a point by a
> scalar can be made about 4 times more efficient than a mod exp
> with a 160 bit q (with some patented technology), for a curve with
> security comparable to that of a subgroup of order 160 bit with p
> 1024 bits.
>
> Hope I gave you enaugh information and hints to work on what you
> wanted to figure out.
>
> -- Anton
>
> Gary Silverman wrote:
> >
> > Without starting a religious war, could anyone comment on relative speed
> > difference between the 3 NIST approaved digital sign algorithms? Please
> > provide a reference if possible.
> >
> > For each, I'm interested in:
> > signing speed
> > verifying speed
> >
> > So, an example could be....
> >
> > RSA DSA ECDSA
> > sign 14 10 8
> > verify 2 20 4
> >
> > The numbers indicate the time it takes for the operation to be done.
> >
> > I realize that different implementations could alter actual performance
> > (in addition to all of the other things like what OS, what kind of
> > hardware, etc...). If anyone has experience using various platforms
> > that would be great too. But, I'm more interested in performance due to
> > the algorithm as opposed to the implementation.
> >
> > Thanks kindly,
> >
> > Gary
>
> --
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: function decomposition
Date: Tue, 15 May 2001 22:17:18 -0700
Tom St Denis <[EMAIL PROTECTED]> wrote in message
news:o1mM6.103182$[EMAIL PROTECTED]...
>
> "Paul Pires" <[EMAIL PROTECTED]> wrote in message
> news:SUlM6.124212$[EMAIL PROTECTED]...
> >
> > Tom St Denis <[EMAIL PROTECTED]> wrote in message
> news:ArlM6.103051$[EMAIL PROTECTED]...
> > >
> > > "Matt Timmermans" <[EMAIL PROTECTED]> wrote in message
> > > news:sdlM6.1840$[EMAIL PROTECTED]...
> > > > Since making ugly decompositions is easy, I assume you're interested
> in
> > > > finding small and elegant ones. You'll want to do a Google search on
> > > > "Karnaugh Maps".
> > >
> > > Nice info. Even ugly ones would interest me now... I'm new to the
> > > decomposition scene.
> >
> > Your new is probably much sharper than mine.
> > If anyone is following this who needs a much more basic book,
> > can I suggest?
> >
> > Beebop to the boolian boogie.
> >
> >
> > No Joke, that's the name.
> >
> > It's a real primer but the author does a great job.
>
> I will look into it... nice site!
It's an eclectic work. He dances all over the place
but it ends up making sense. Truth tables and Karnaugh Maps,
Epitaxial fab techniques, FPGA's. It's a fun ride.
Paul
>
> I manged to make an unoptimized copy of my TC15 box using pure boolean logic
> gates (no sequential stuff). It's huge but what the heck...
>
> http://tomstdenis.home.dhs.org/decomp.c
>
> That source will decompose and output C code that implements the sbox.
>
> Tom
>
>
------------------------------
From: Gary Silverman <[EMAIL PROTECTED]>
Subject: Re: best algo
Date: Wed, 16 May 2001 00:30:28 -0500
Tom St Denis wrote:
> "Nils Johansson" <[EMAIL PROTECTED]> wrote in message
> news:9dpdb8$j0gbf$[EMAIL PROTECTED]...
> > cant deffie-hellman be used to distribute the key
> >
> > I need something more secure, because anyone might be listening, and catch
> > the key. I dont want to involve a third part either...
>
> Well typically (i.e. in theory) DH is very secure. It's completely
> vulnerable to mitm attacks though...
Is it vulnerable to mitm attack even if the two participants already know the
"public data" necessary to form the session key? I'm relatively new to this, so
I want to make sure I understand what the vulnerability really is. I've read
that the public data could be a simple as using another entity's public
certificate. If I know the certificate I'm inspecting is authentic - is DH
secure?
Or, is the point that typically I _don't_ know that the certificate I'm
inspecting is really from the party I wish to establish a secure connection
with, because after I request the certificate, "mitm" will replace the
"authentic" one with his own. Is this why it's insecure?
Please advise. You may also respond directly to mailto:[EMAIL PROTECTED]
Thanks.
>
>
> Tom
------------------------------
Date: Tue, 15 May 2001 22:45:45 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Subject: Re: What Is the Quality of Randomness?
=====BEGIN PGP SIGNED MESSAGE=====
Tim Tyler wrote:
> Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
>
> : There is no such thing as a random sequence, only a random source.
>
> Well, "random sequence" is a meaningul term - provided one uses the
> notion of randomness that derives from Chaitin and Kolmogorov, rather
> than from Shannon.
The usual term is "[Chaitin-]Kolmogorov complexity", which as the name
implies is a measure of complexity, not randomness or entropy (although
it is not completely unrelated: on average, a source with high Shannon
entropy will tend to produce strings with high Kolmogorov complexity).
In cryptography we normally need to assess the strength of generators,
not particular strings, so Shannon entropy is the appropriate concept
to use.
- --
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
iQEVAwUBOwGjcTkCAxeYt5gVAQEQvAgAkDcSMr/6tIPqo8YH/dmzYUzr37trDM+z
yOlednrXFtA8jyEZm19XvJtSnV8rHcMH/ZUvGH3hVV07aytR/FrFyhkLuK8j9YK4
hD5frQxeiqFHfPLAn8tWER+aDjx9bAvYnfpvD4+afX1OjdDFPSDyrGrpnFSuSVJZ
7NKSf3yGR6k5ILThh7mkzZCtoYxE6jYdUJsyDNRQ46OwFZaPafpQbAQAplN1Ukla
717XxI73OhLBRJwhry0d4dDmRQscDaaMEQ5dNJzRPkJyBlqVjdRGLWzYA8gTChG1
Gm/kHHBRGdrS/o2o6jhV2FHS+sfIqavZ/Ok/MBeC0QJeaTm4SpyBkQ==
=flNw
=====END PGP SIGNATURE=====
------------------------------
Date: Wed, 16 May 2001 03:47:05 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Subject: Re: Are low exponents a problem with RSA?
=====BEGIN PGP SIGNED MESSAGE=====
DJohn37050 wrote:
> Use of a larger RSA public exponent might help to protect against the r=
isk
> of an RNG failure. For example, if the RNG is STUCK at a constant valu=
e,
> this it is NO value at all and the OAEP or whatever formatted messages =
will
> be related, which is a concern.
Obviously it invalidates the security proof (the fixed version by Fujisak=
i,
Okamoto, Pointcheval, and Stern), but I would be surprised if there were =
any
practical attack on OAEP due specifically to using low exponents with a
broken RNG.
Clearly, no public key encryption scheme can be secure against plaintext
guessing (a.k.a. forward search) attacks if it is deterministic, as will =
be
the case with a completely stuck RNG. So this is not a reason to choose f=
ull
exponents over low exponents, because it applies to both.
The version of OAEP standardised in IEEE Std 1363-2000 and PKCS #1 v2.0 i=
s
this:
OAEP(r, M, P) =3D (DB XOR G(r)) || (r XOR H(DB XOR G(r)))
where DB =3D h(P) || 0^k || 1 || M
P =3D encoding parameters (often zero length)
If the RNG is stuck, then the effect is basically to XOR the message
(encoded as DB) with the fixed pseudorandom string G(stuck_r), then
append a a hash of this at the low-order end, so that the RSA block is
filled. Even this very simple masking can reasonably be expected to be
quite effective at preventing H=E5stad and similar related-message attack=
s,
as long as the messages are not chosen to depend on G(stuck_r). Of course=
if an attacker chooses messages, it could make their encodings linearly
related, but that is not a useful attack (being able to *recognise* a
message with an encoding linearly related to one chosen by the attacker
is also not useful, because forward search as discussed above is a more
efficient way of doing that).
There is even less reason to be concerned about OAEP with an RNG that
is weak, but not completely stuck. Notice that r never appears directly
in the OAEP output (i.e. the RSA function input), except XOR'd with the
output of a hash. Provided the RNG outputs different seeds for different
messages, then the OAEP outputs will be "random looking" and effectively
independent (or at least not linearly related), regardless of whether the=
messages are related. It should not even be possible to recognise
identical messages, provided the seed cannot be brute forced (typically
the seed length is 160 bits, so there is scope for some bias without
allowing brute force).
> If the "random" output is related, then it depends on the details.
The important point is whether the OAEP outputs are related in an
exploitable way, i.e. in a way that interacts badly with the RSA function=
,
to a greater extent for low exponents than for full exponents. That seems=
unlikely, considering the details of how OAEP is defined.
> Note that this is not just a theoritical possibility, apparently the
> Russian VERONA transcripts were using a OTP and somehow the OTP was
> caused to repeat or the RNG repeat or something.
That's a very different case: VENONA relied on biases and repeats in a
stream that was directly XOR'd against the message. The security of an
OTP relies critically on the keystream being uniformly and independently
distributed; the security of RSA-OAEP does not rely on the same for the
seed. (In general, the extent to which a cryptographic scheme or protocol=
relies on the quality of its random inputs can vary dramatically; for
example DSA *does* rely on uniformly and independently distributed seeds,=
as shown by the recent attacks.)
In summary, I don't think that potential RNG problems are a good reason
for choosing full exponent RSA-OAEP over low exponent RSA-OAEP. Choose
whether to use low exponents based on performance requirements and other
security arguments.
- -- =
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 0=
1
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 b=
een
seized under the Regulation of Investigatory Powers Act; see www.fipr.org=
/rip
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOwHphjkCAxeYt5gVAQHEhwf7BNEiWjuuN5podXwKaTj2CUhR0iVAWyvo
X5HMDBKXV6l45OlSJFHCritn/nLfvsfQYkXun29Ch4pVq/p4UMQ3E4p3l+cs2QTh
dig7fvH93aqvP/sB6AwCwnxVPHdvR04LgOwyomFSoF6FAQAivi0agTWlXaaTHqv2
P+TQ/n719L9iJc3WRri1x65umSrC/hSSCUX/2JKj7tAzVVVs1RZOsNnno4uLllOe
sK4fP9rM/QENm1IKs+z4WFXvrRl1YnCm+iTP1iqGuIcuC1IViP1J3HMLe83KXUJJ
P88bbw57HO7DmR/l7J6zDhVWaJCmAJ7n2vpEjH7HiyCdwGOoOqLVNQ=3D=3D
=3DvScZ
=====END PGP SIGNATURE=====
------------------------------
Date: Wed, 16 May 2001 06:19:44 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Subject: Re: Key escrow based on BBS
=====BEGIN PGP SIGNED MESSAGE=====
Tom St Denis wrote:
> I was wondering after all the Key Escrow debackle in the mid 90s has an=
yone
> suggested this trivial solution?
The "key escrow debacle" was not about whether it was technically possibl=
e
to escrow keys assuming the co-operation of all potential users. The
disagreement was about whether it was useful, secure, or desirable to do
so, and about whether any criminals would co-operate.
Every so often I still see papers propose some variant of centralised key=
escrow (for example in [BF01], which otherwise includes some very useful
and interesting ideas). I wonder why they bother - the argument for key
escrow has been thoroughly lost. Even supposedly consensual key recovery
(cf. the ADK feature in PGP) causes more security problems than it is wor=
th.
Secure backup of keys in such a way that they can be restored by the owne=
r
is one thing; creating deliberate side doors [*] in cryptosystems is quit=
e
another.
[The standard counter, particularly for encryption in business contexts, =
to
the assertion that only a key holder should have access to their key, is
"What happens if the key holder dies?" I'm not at all convinced by that
argument - if there is information essential to the running of a business=
,
what was it doing encrypted to an individual in the first place? It proba=
bly
should have been encrypted to a set of keys associated with a r=F4le, so =
that
it can be decrypted by any current holder of that r=F4le. An important
difference between that and key recovery is that there is never a master
key that can decrypt any message. For strictly personal data, OTOH, if a
person doesn't want to provide any way to decrypt that data after their
death, then what exactly is the problem?]
BTW, your Elgamal/BBS-based protocol doesn't achieve anything more than
encrypting K again with the escrow agent's public key, and is more comple=
x.
[*] A back door is a way of bypassing a security mechanism that is kept s=
ecret.
A side door is a way of bypassing a security mechanism that the desig=
ner
tries to convince you that you wanted.
[BF01] Dan Boneh, Matthew Franklin,
"Identity-Based Encryption from the Weil Pairing,"
http://crypto.stanford.edu/~dabo/abstracts/ibe.html
- -- =
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 0=
1
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 b=
een
seized under the Regulation of Investigatory Powers Act; see www.fipr.org=
/rip
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOwINnDkCAxeYt5gVAQG2lwf8DvEoYbMSDCjK040qh2fDJlhYHNl2+1p/
Zhq5O2wCwwoXSteNNVu/eaF3v8Nt330OMyW51OAAZIljbbx7syUEJFacTq5rKJzd
+mdFT3vRPYgP8eW3xrcGhaLsvA7Lo3uL+dmuQbUagsahfb3jTCOpQdC+m94+Jxnj
fv9L4QWvqbDwEHbdN7MkaBeT0Nr4wr0I88ryvw/QReosSanUEfbwD173O6PuYPb2
NSXSDG50Hy/klg1SIfzOvzsddJg2M8LbLOp5w7PLImSSVRyXbYwYmj0P6sWsc9YS
fOf8x4ZT4jw+nZg51u0Dr4yQjpOgtHWv3xdGpZE4d1mtmCVQAW81BA=3D=3D
=3DIlbu
=====END PGP SIGNATURE=====
------------------------------
Date: Wed, 16 May 2001 06:25:25 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Subject: Re: OAP-L3: "The absurd weakness."
=====BEGIN PGP SIGNED MESSAGE=====
[alt.hacker and talk.politics.crypto removed, since this is off-topic there.]
Anthony Stephen Szopa wrote:
> James Felling wrote:
> > I have pointed this out to you in the past, and while I do accept that
> > using your medhods over and over again you can and will eventually get
> > good data, it requires more work to get to that point than it would with
> > a conventional stream cypher.
>
> Are you are under the delusion that the OTPs are derived directly
> from the random digit output?
As I said in one of my previous posts,
# There's little point in telling Szopa [that the permutation methods are
# weak], though; people have done that before, but he tries to claim that
# the output stage will hide the non-randomness in the permutation table.
# AFAICS (from an admittedly brief analysis), there is no reason to believe
# that it does, and I would be surprised if there were not a distinguisher
# using only a small amount of output.
If you really want us to analyse the output stage in more detail (which I
doubt), then post a *clear* description of it here - I found the description
on the web site somewhat vague. I don't see why anyone would want to rely
on it to save the obviously flawed main stage, where almost all of the
entropy is input, 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
iQEVAwUBOwIO/zkCAxeYt5gVAQHZ/QgAyo2rbZ6Xg0EsOFiyR+EQ3YD8/pTjZrUR
dG7ztYmJEJa1ZtNlSz0pg1g7jCrnq3b8iQV6QvAli7uw2/iun7dGGIT82VxAq7jz
hn1oD2UFZ61atI6q0yj9FAZ1KkvIcb73PpPUjkQvOqys9ZQjZTr5beBu6aE4l2AZ
ilZNyjVHJYCy6viPw92ymNHN8XSkdJexB/z4wZ3JSQj8gr5qJuY82JPylRfmeEv8
wwMd8wcMrFjIw05FH4NaiXF1GReLJkFUM0cEmBrtc9HJKFDCUjgJ3z065THGkWek
K2thQ/Bces5RaEKn/cqg1Wmi+EAXrnP/LC9P3SVM8cPyK1iWFdP3PQ==
=fJzw
=====END PGP SIGNATURE=====
------------------------------
** 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
******************************
