Main Page | Report this Page
 
   
Science Forum Index  »  Cryptography Forum  »  RSA vs DH
Page 5 of 6    Goto page Previous  1, 2, 3, 4, 5, 6  Next
Author Message
Roger Schlafly
Posted: Sun Dec 21, 2003 3:09 am
Guest
"Paul Crowley" <paul@JUNKCATCHER.ciphergoth.org> wrote
Quote:
If I want many people to use the same parameters for their keys, then
I can use the "official" method to generate them, and display the seed
and count to prove that they were generated with this method. This
would make imposing cooked DSA parameters extremely difficult.

Yes, that is right. And it is rare for anyone to need to verify that the
generation method was used. I suppose that some paranoid person
could do it when a CA hands him some parameters and he generates
a key and applies for a cert. But for routine communications, it is
just not needed.
Roger Schlafly
Posted: Sun Dec 21, 2003 3:11 am
Guest
"DJohn37050" <djohn37050@aol.com> wrote
Quote:
If the DP are invalid, basically all bets are off, including validation of
the
subgroup order of a public key meaning anything. Roger, of course, can
choose
to be as insecure as he wants to be.

Yes, and anyone else can be as insecure as he wants to be. Get over it.
Roger Schlafly
Posted: Sun Dec 21, 2003 3:19 am
Guest
"Paul Crowley" <paul@JUNKCATCHER.ciphergoth.org> wrote
Quote:
I was under the impression that for the same key sizes, DL and
factorization were around the same difficulty, which would suggest
that factorization has only been extended to longer keys because it is
the more famous problem. ...

Not true. DL is harder. The methods are similar, with a phase I and
a phase II. Most of the CPU time is spent on phase I, and DL is
only slightly harder than factoring. Phase II is pretty fast if you have
a lot of RAM. DL requires a whole lot more RAM than factoring
in phase II. With current technology, this limits the size of the DL
problem that can be solved.

Some models measure hardness differently. Eg, if you assume that
infinite RAM has zero cost, then DL problems are not much harder
than factoring.
DJohn37050
Posted: Sun Dec 21, 2003 9:27 am
Guest
The point is NIST and Roger S. appear to differ on assurance reqs. for DP and
public keys. I go with NIST. For DSA, you MUST have a seed to show arbitrary
gen, if you are trusting of a TTP, you can use that trust for the TTP's
assertion of correctness. BTW, in the new draft, g will be able to be gen'ed
from the seed.
Don Johnson
Paul Crowley
Posted: Sun Dec 21, 2003 9:28 am
Guest
ggr@qualcomm.com (Gregory G Rose) writes:

Quote:
In article <q8UEb.4922$Ep2.958295183@twister1.starband.net>,
Roger Schlafly <rogersc@mindspring.com> wrote:
"Gregory G Rose" <ggr@qualcomm.com> wrote
I don't think we were referring to checking the
group parameters. We were referring to checking

I think Don wanted to check the group parameters.

(a) damn this newsfeed... I only ever have half
the context.

(b) even so... to check that a particular D-H
public key is in the order-q (for whatever large
prime q it is that divides p-1) subgroup, you have
to know the factorization of p-1, and to know that
it either has to be built in, or provided by the
other end in which case you should check it, or
you have to factor p-1 at the client which is
really a big ask...

So I still refute the statement that there's no
point checking parameters.

Nitpick: "reject", not "refute"!

You don't need to know the whole factorisation, you just need to know
q. I guess I was thinking that q was one of the parameters; I tend to
assume that people usually work in the Schnorr group. But anyway,
this is sort of different - you're talking about defending against
attacks, which is good and sensible, not against incompetent
implementation, which is a losing game.
--
__ Paul Crowley
\/ o\ sig@paul.ciphergoth.org
/\__/ http://www.ciphergoth.org/
Roger Schlafly
Posted: Sun Dec 21, 2003 1:32 pm
Guest
"DJohn37050" <djohn37050@aol.com> wrote
Quote:
The point is NIST and Roger S. appear to differ on assurance reqs. for DP
and
public keys.

Not true. Show me the NIST document that disagrees with anything I said.
DJohn37050
Posted: Sun Dec 21, 2003 2:31 pm
Guest
Roger, you have to come to X9F1 meetings to get it, but you can see the trend
at the old KES doc.

Don Johnson
Roger Schlafly
Posted: Sun Dec 21, 2003 2:48 pm
Guest
"DJohn37050" <djohn37050@aol.com> wrote:
Quote:
The point is NIST and Roger S. appear to differ on assurance reqs. for
DP
and public keys.
Not true. Show me the NIST document that disagrees with anything I said.
Roger, you have to come to X9F1 meetings to get it, but you can see the
trend
at the old KES doc.

So you claim that NIST disagrees with me, but not in any of the 100s of
official documents on the NIST web site. The only way I can detect this
alleged disagreement is to attend some X9F1 meetings and listen carefully
to some oral comments. Or maybe if I can read between the lines in some
other documents, I might detect a trend towards a potential disagreement
with me.

Yes, I detect a trend. The trend is that you cannot post any support
for what you say.
DJohn37050
Posted: Sun Dec 21, 2003 3:49 pm
Guest
I report on the DSA draft from NIST as I understand it. Obviously, I do not
represent a TTP to Roger. The KES (key establishment schemes) draft 2 (Jan
2003) on the nist web site does discuss the need for assurance of DP and public
keys. See TOC extract below.

5. Cryptographic Elements
...........................................................................
.........................12
5.1 Domain
Parameters................................................................
......................................... 12
5.1.1 Domain Parameter
Generation................................................................
............ 13
5.1.1.1 FFC Domain Parameter
Generation.................................................... 13
5.1.1.2 ECC Domain Parameter
Generation................................................... 13
5.1.2 Assurances of Domain Parameter
Validity........................................................ 14
5.1.3 Domain Parameter
Management................................................................
......... 15
5.2 Private and Public Keys
...........................................................................
........................ 15
5.2.1 Private/Public Key Pair
Generation...................................................................
15
5.2.2 Assurances of the Arithmetic Validity of a Public
Key..................................... 15
5.2.2.1 Owner Assurances of Static Public Key
Validity............................... 16
5.2.2.2 Recipient Assurances of Static Public Key
Validity........................... 16
5.2.2.3 Owner Assurances of Ephemeral Public Key
Validity....................... 17
5.2.2.4 Recipient Assurances of Ephemeral Public Key Validity
................... 17
5.2.2.5 FFC Full Public Key Validation Routine
............................................. 17
5.2.2.6 ECC Full Public Key Validation Routine
............................................ 18
5.2.2.7 ECC Partial Public Key Validation Routine
........................................ 18
5.2.3 Assurances of Possession of Private Key
........................................................... 19
Don Johnson
DJohn37050
Posted: Sun Dec 21, 2003 3:56 pm
Guest
Annex C of X9.30 Oct 2003 draft
(Normative)

Assurance
C.1 Assurance of Domain Parameter Validity
C.1.1 Introduction
The DSA depends on the arithmetic validity of the domain parameters. Each
entity (i.e., signatory and verifier) shall have assurance of the validity of
the domain parameters prior to the generation of a digital signature key pair x
and y, and the generation and verification of a digital signature. Note that
users of the domain parameters must have assurance that the domain parameters
are valid for the lifetime of any keys that are associated with the domain
parameters.
Each entity shall obtain assurance that the domain parameters are valid using
at least one of the following methods:
1. The entity itself generates the domain parameters according to the
specified requirements (see Section 8.3.2).
2. The entity performs an explicit domain parameter validation as
specified in Annex C.1.2.
3. The entity has received assurance from a trusted third party (e.g., a
CA) that the domain parameters were valid at the time that they were generated
because the trusted third party either generated the domain parameters, or has
performed an explicit domain parameter validation as specified in Annex C.1.2.
Also, see Annex C.1.3.
C.1.2 Explicit Domain Parameter Validation
Domain parameters can be explicitly validated using the following procedure or
its equivalent if p, q, g, domain_parameter_seed, and counter are known:
The following process or its equivalent shall be used to explicitly validate
domain parameters.
domain_parameter_validation(...):
Input: integers L and N, domain parameters (p, q, g, , domain_parameter_seed,
counter)
Output: string "Valid" or "Invalid"
Process:
1. Verify that the (L, N) pair are valid, i.e., that (L, N) is either
(1024, 160), (2048, 224), (3072, 256), 8192, 384) or (15360, 512). If (L, N) is
not in the list, then Return ("Invalid").
2. Verify whether p and q were generated using one of the prime generation
algorithms specified in Annex A.1 . The validation process is also described in
Annex A.1. If the prime validation algorithm returns "Invalid", then Return
("Invalid"). Otherwise, go to step 3.
3. If a TTP generated the generator g using the technique specified in
Annex A.3.2, then go to step 4. Otherwise, go to step 5.
4. Perform a partial validation of g using the process specified in Annex
A.3.3. If "Partially valid" is returned, then Return ("Valid"). Otherwise,
Return ("Invalid").
5. If a TTP generated the generator g using the technique specified in
Annex A.3.4, or an entity other than a TTP generated the domain parameters,
verify that g was generated using the canonical technique in Annex A.3.4 by
performing the validation process specified in Annex A.3.5. If this process
returns "Invalid", then Return ("Invalid"). Otherwise, Return ("Valid").
C.1.3 Assurance When Domain Parameters are Generated by Another Party
C.1.3.1 Discussion
There are two basic scenarios for DSA parameter generation: generation by a
trusted party and generation by a non-trusted party.
When domain parameters are generated by a trusted party, all the users in a
domain trust the same party (a Trusted Third Party, or TTP) to generate and/or
select valid sets of domain parameters, and the TTP is trusted to generate
domain parameters correctly. If a new set of domain parameters is needed, it
is generated or selected by the TTP. The TTP certifies the validity of all sets
of domain parameters that are used in its domain. Note that users outside the
domain may not have the same level of trust in the TTP of that domain; that is,
this scenario does not necessarily have transitive trust.
When domain parameters are generated by an untrusted party, an untrusted party
creates or selects a new (candidate) set of domain parameters. It is
conceivable that the untrusted party may not generate domain parameters
correctly; in fact, an untrusted entity may be an adversary who is trying to
gain an advantage. In this case, the domain parameters shall be generated so
that they can be validated as being correct. That is, the domain parameters
shall be generated so that any entity can validate the (candidate) set of
domain parameters as being valid. This scenario allows trust to be established
outside of a single domain; it is said to allow for "transitive trust".
There are different methods of obtaining assurance of domain parameter validity
in each scenario.
C.1.3.2 Assurance When Domain Parameters are Generated by a Trusted Party
In this scenario, an entity shall receive assurance of domain parameter
validity from a third party that is trusted by that entity (i.e., a TTP).
However, the TTP must decide how to obtain this assurance for itself. Examples
of methods that the TTP may use to obtain this assurance are as follows:
a. The TTP generates the set of domain parameters.
b. The TTP selects the set of domain parameters from a list published by
an entity that the TTP trusts.
c. The TTP performs explicit domain parameter validation as specified in
Annex C.1.2 and obtains a result of "valid".
C.1.3.3 Assurance When Domain Parameters are Generated by an Untrusted
Party
In this scenario, an entity shall obtain assurance of domain parameter validity
using at least one of the following methods; the first two methods are
preferred:
1. The entity performs explicit domain parameter validation as specified
in Annex C.1.2 and obtains a result of "valid".
2. The entity receives assurance from a third party that is trusted by
that entity (i.e., a TTP) that the TTP performed an explicit domain parameter
validation as specified in Annex C.1.2 and obtained a result of "valid".
3. The verifying entity trusts an assertion by the signatory that the set
of domain parameters are valid (e.g., the domain parameter routine resides in a
FIPS 140-2 validated cryptographic module and was tested during the validation
process). This is known as owner assertion of validity, as the signatory is
the owner of the private key.
C.2 Assurances of Key Pair Validity
C.2.1 Introduction
The correct functioning of the DSA depends on the arithmetic validity of the
public/private key pair that is used for digital signature generation and
verification. Each signatory uses the private key x of a key pair to generate a
digital signature; the signatory shall have assurance that the key pair has
been correctly generated. Each verifier uses the public key y to verify a
digital signature that was generated by the signatory using the associated
private key x; the verifier shall have assurance of the validity of the public
key.
C.2.2 Signatory Assurances of Key Pair Validity
The signatory shall obtain assurance of key pair validity using one or more of
the following methods. The most assurance is provided when method 1 is combined
with method 2 or 3.
1. Signatory generation. The signatory generates the key pair as specified
in Section 8.4.2.
2. Signatory Full Validation. The signatory performs a full public key
validation (see Annex C.2.4).
3. TTP Full Validation. The signatory receives assurance that a trusted
third party (trusted by the signatory) has performed a successful full public
key validation (see Annex C.2.4).
4. TTP generation. The signatory receives assurance that a trusted third
party (trusted by the signatory) has generated the key pair and provided it to
the signatory. This method is not preferred, since the TTP will know the
private key and must be trusted not to masquerade as the signatory.
The signatory shall know which method(s) of assurance were used in order for
the signatory to determine that the provided assurance is sufficient and
appropriate to meet the signatory's requirements.
C.2.3 Verifier Assurances of Public Key Validity
Assurance of a public key's validity shall be provided to the verifier using
one or more of the following methods; the first two methods are preferred.
1. The verifier performs a full public key validation as described in
Annex C.2.4.
2. The verifier receives assurance from a TTP (e.g., a CA trusted by the
verifier) that the TTP has performed a full public key validation as described
in Annex C.2.4.
3. The verifier receives assurance that a TTP (e.g., a CA trusted by the
verifier) has generated or regenerated the public key using trusted routines.
This method may impact the non-repudiation property that is be desired for some
signatures, as the TTP will know the private key and must be trusted not to
masquerade as the signatory.
4. The verifier trusts an assertion by the signatory that the signatory's
keys are valid (e.g., the key pair generation routine resides in a FIPS 140-2
validated cryptographic module and was tested during the validation process).
The verifier shall know which method(s) of assurance were used in order for the
verifier to determine that the provided assurance is sufficient and appropriate
to meet the verifier's requirements.
C.2.4 (Explicit) Full Public Key Validation
Public key validation is the process of checking whether the public key is in
the correct multiplicative subgroup of the field that is specified by the
associated domain parameters. Public key validation does not require knowledge
of the associated private key, so may be performed by anyone.
The following process or its equivalent shall be used to validate a digital
signature key pair when public key validation is required:
Public_Key_Validation(...):
Input: integer domain parameters (p, q, g), integer public key y
Output: "Valid" or "Invalid"
Process:
1. Verify that 2 £ y £ p-2.
(Ensure that the key has the unique correct representation and range in the
field)
2. Verify that yq º 1 mod p.
(Ensure that the key has the correct order in the subgroup)
3. If either of the above checks fail, then Return ("Invalid"). Otherwise,
Return ("Valid").
C.3 Assurances of Possession of the Private Key
C.3.1 Introduction
The authenticity of digital signatures depends on the claimed owner of a public
key possessing the private key associated with that public key. The term
'claimed owner' is used to indicate that the expected owner may not actually
possess the private signature key, due to any number of reasons (e.g., an error
during key pair generation or an attack by someone pretending to be the owner).
As assurance of private key possession is not meaningful without assurance of
public key validity, the assurance of the validity of a public key shall be
obtained either prior to or concurrent with obtaining assurance of possession
of the associated private key.
C.3.2 Owner Assurances of Possession of a Private Key
The claimed owner of a public key shall have assurance that he/she currently
possesses the associated private key in one or more of the following ways:
1. Owner Receives Explicit Confirmation - The claimed owner has generated
a digital signature that was successful verified by a trusted party (trusted
by the owner, including possibly the owner itself). The confirmation process
shall include information that indicates that the owner currently possesses the
private key, e.g., by including a challenge response procedure or a timestamp.

2. Pair-wise Consistency - The owner has verified that the private key is
the inverse of the public key. This may be accomplished by the claimed owner
of a signature key pair generating a signature and then verifying the signature
himself/herself.
3. Owner Regeneration - The claimed owner has regenerated the
public/private key pair using different routines or a different processor from
that used during the original generation process. The regenerated private and
public key shall be equal to the originally generated private and public key.
4. Trusted Provision - A trusted party (trusted by the owner) has provided the
private key and public key to the claimed owner. The use of this method
implies that the owner trusts the trusted party not to use the private key to
masquerade as the owner, and that the trusted party has performed any tests
needed to assure itself that the claimed owner possesses the associated static
private key. For example, this method may be appropriate for an individual in
an organization if the individual is representing the interests of the
organization, and the organization is the TTP that generates the key pair.
The owner shall know which method(s) of assurance were used in order for the
owner to determine that the provided assurance is sufficient and appropriate to
meet the application's requirements.
C.3.3 Recipient Assurances of Possession of a Private Key
A recipient shall have assurance of the claimed owner's possession of a private
key that is associated with a public key in one or more of the following ways:
1. Recipient Receives Explicit Confirmation - The recipient receives
assurance that a trusted party (trusted by the recipient) has performed a
successful verification of a digital signature generated by the claimed owner.
The confirmation process shall have included information that indicates that
the owner possessed the private key at the time that the confirmation process
was performed, e.g., by including a challenge response procedure or a
timestamp.

2. Trusted Provision - The recipient receives assurance that a trusted
party (trusted by the recipient) has provided the private key to the owner.
Note that trusted provision means the recipient trusts the trusted party not to
use the private key to masquerade as the owner. This method may be appropriate,
for example, when the recipient is in the same organization as the signatory,
and the organization is the TTP that generates the key pair.

A recipient shall know which method(s) of assurance were used in order for the
recipient to determine that the provided assurance is sufficient and
appropriate to meet the application's requirements.
C.3.4 Recipient Initial Assurance via Explicit Owner Assertion
The recipient receives assurance from the claimed owner that the private key
associated with the public key is actually owned by that entity. For example,
this assurance may be through the use of the owner's digital signature on a
certificate containing the public key (i.e., a self-signed certificate). This
method is appropriate only in order to initiate the process of obtaining a
higher level of assurance for the recipient through one of the methods above.
That is, this weak level of assurance is only appropriate to initiate the
process of obtaining further assurance as specified in Appendix C.3.3.





Don Johnson
Bodo Moeller
Posted: Sun Dec 21, 2003 8:39 pm
Guest
David Wagner <daw@taverner.cs.berkeley.edu>:

Quote:
A follow-up point: If one wants better than 80-bit security, does
anyone know whether it is possible to use the UOWHF trick with DSA?

In other words, this would involve replacing H(M) by H(N, M) where
N is a random nonce chosen by the signer and included with the signature.
With this modification, the ability to find collisions in SHA1 doesn't
seem to help forge signatures. (Ok, it allows the signer to come up with
a pair of messages that have the same signature, but this isn't a problem
so long as we agree that the signer is bound by any signature that matches
her public key.) Does this work? Is it secure?

This approach, where H(M) is replaced by H(N || M) during DSA
signature generation and verification, works and is secure in the
sense that

- any chosen message attack against DSA-with-nonce directly yields a
chosen message attack against standard DSA (what DSA-with-nonce does
is really just generating a standard DSA signature on the
concatenated string N || M), and

- finding a random hash function collision by a birthday attack does
not allow a successful chosen message attack as it would for DSA.

Now these two points do not imply that DSA-with-nonce is really
more secure than standard DSA -- it just can't be less secure, and
the *specific* attack that we tried to avoid is avoided.

To illustrate what the latter means, let us consider the
DSA-with-nonce variant where H(M) is replaced by H(M || N) rather
than H(N ||M). This variant would similarly achieve the above two goals,
but it is really just as vulnerable as standard DSA against birthday
attacks for SHA-1 or any other hash function using the usual cascade
construction because the adversary wouldn't have to worry about N
while searching for a collision (if two prefixes M, M' of identical
length result in a collision within the cascade, then
H(M || N) = H(M' || N) for any string N).


Quote:
If this idea does work, it might be possible to use a subgroup of size
up to 320 bits, while still sticking a hash based on SHA1, in case you
have more confidence in SHA1 than in SHA256 or SHA512.

It appears to work (with some modest security guarantees, but then DSA
is not about provable security anyway *eg*). For practical purposes,
instead of using an eplicit nonce N such that a signature on M
has the form (N, r, s), it looks tempting to use r as the nonce
(remember that r = (g^k mod p) mod q with a random k); however,
then standard DSA would no longer occur as an atomic ingredient,
so this modification would void the security argument.

One might want to try the following approach, though ...: make DSA
signing deterministic by generating k as G_1(x || M) where
x is the secret key and G_1 is an instantiation of a random oracle
(this might make sense for standard DSA anyway because it gets rid of
the need for a secure random number generator for signing), and
compute N from r as G_2(r) where G_2 is an instantiation of a
second random oracle. So signatures keep the short form (r, s),
and the hash to be computed during both signing and verification
is H(G_2(r) || M). It looks not totally unreasonable to suspect that
this scheme can be proven secure in the random oracle model, assuming
that DSA is secure (verifying this conjecture is left as an exercise).
Once this has been proven, it shouldn't require a large leap of faith
to assume that the new scheme is actually more secure than DSA as long
as G_1 and G_2 are polite enough to pretend to be random.
Roger Schlafly
Posted: Mon Dec 22, 2003 2:56 am
Guest
"Bodo Moeller" <moeller@cdc.informatik.tu-darmstadt.de> wrote
Quote:
This approach, where H(M) is replaced by H(N || M) during DSA
signature generation and verification, works and is secure in the
sense that ...

Alternatively, one could decide to only sign messages where he
has had a chance to put his own header on (with a random nonce).
Michael Amling
Posted: Mon Dec 22, 2003 9:10 am
Guest
Paul Crowley wrote:
Quote:
"Roger Schlafly" <rogersc@mindspring.com> writes:

There is no reliable way to check either her competence or her
parameters. It is possible to construct weak DSA parameters, but
she would have to do so willfully.

If I want many people to use the same parameters for their keys, then
I can use the "official" method to generate them, and display the seed
and count to prove that they were generated with this method. This
would make imposing cooked DSA parameters extremely difficult.

If by the "official" method you mean the one in appendix 2 of
FIPS-186-2, then being handed the seed and resulting parameters does not
really prove they are uncooked. The method begins with "Step 1. Choose
an arbitrary sequence of at least 160 bits and call it SEED." Someone
may have tried untold billions of such seeds before finding one that
generated parameters with certain properties. While they may not be
fully cooked, they could be warmed over or at least above room temperature.
If the seed looked like "5061756C 2043726F 776C6579 00000001", then
I'd believe that it hasn't been selected maliciously from a large set of
tested seeds.

--Mike Amling
David Shaw
Posted: Wed Dec 24, 2003 11:24 am
Guest
David Wagner <daw@taverner.cs.berkeley.edu> wrote:
Quote:
Lack of software support would be troubling, I agree. Is it really
true? Do people really write software that takes special pains to
bail out if your DSA key is larger than 1024 bits? Does OpenSSL do
this, for instance? If so, how disappointing. (I don't think gpg
does, for instance...)

GnuPG does the conservative thing and accepts >1024 bit DSA keys
generated elsewhere, but refuses to generate them itself.

David
David Shaw
Posted: Wed Dec 24, 2003 12:03 pm
Guest
Paul Rubin <http://phr.cx@nospam.invalid> wrote:
Quote:
Tom McCune <tom@DELETE_THISmccune.cc> writes:
DH(EG) encryption is very much slower than RSA encryption.
DH(EG) decryption is about twice as fast as RSA decryption.
Unless you use canned primes (the default for PGP) for DH key generation,
RSA key generation is very much faster that DH(EG) key generation.

It didn't occur to me that anyone generates a new field at keygen
time, or that the key format even included a way to specify the field.
GPG doesn't present the option of generating a new field when you
generate an EG key the normal way, though there might be some advanced
command that does it. There's really no reason to do it. If you're
paranoid enough to think that an attacker can break DLP over the
canned field, you ought to expect they can also break it over a newly
generated field.

GnuPG doesn't use canned primes, but as you say, it doesn't matter
much.

David
 
Page 5 of 6    Goto page Previous  1, 2, 3, 4, 5, 6  Next   All times are GMT - 5 Hours
The time now is Sun Oct 12, 2008 10:15 pm