Prev: What do I need to know to design a cryptosystem?
Next: Is this construct a MAC ?
From: Greg Rose on 13 May 2010 10:28
In article <20100513063338.0ed9a326(a)tritium.streitmacht.eu>,
Ertugrul Söylemez <es(a)ertes.de> wrote:
>ggr(a)nope.ucsd.edu (Greg Rose) wrote:
>
>> In article
><d5be07db-9929-4c15-8415-f0185fea33bd(a)e34g2000pra.googlegroups.com>,
>> Bryan <bryanjugglercryptographer(a)yahoo.com> wrote:
>> >Ertugrul Söylemez wrote:
>> >> In general, it's considered best to pick the largest subgroup.
>> >
>> > No, currently practice is to pick a base that generates a subgroup
>> > of large prime order. When the modulus is safe prime 'p',
>> > cryptographers tend to choose a base that generates a subgroup of
>> > prime order q=(p-1)/ 2. That said, I don't know of any security
>> > problem with your advice to pick a safe prime and a generator of the
>> > entire group.
>>
>> I guess it depends what you want to do with the answer, and I don't
>> think the OP actually said. If it is for Diffie-Hellman, though, there
>> is a reason to prefer using the prime-order subgroup. Note that it's
>> straightforward to figure out which subgroups a group element is in,
>> and that for a safe prime the order q subgroup is exactly elements
>> that are squares. Suppose you use a generator of the entire group, in
>> general. Alice intentionally chooses a square, and does D-H with
>> Bob. Now if the result of the D-H is a square, Alice knows that Bob
>> chose a square too; otherwise he didn't. This is one bit of
>> information that Alice shouldn't have, and can't be concealed. Worse,
>> if the D-H is in the clear, anyone can tell that one bit of
>> information about both Alice and Bob's choices.
>>
>> [...]
>>
>> Basically, it's always safest to use the
>> large-prime-order subgroup in this and most other
>> contexts.
>
>I already noted that a modulus of b bits gives a strength of b - 1 bits
>effectively, so I took that into account. You lose that bit, no matter
>what you do. If you use the prime order subgroup, you reach only half
>of all elements. If you use the full group, the above attack is
>applicable.

I think it's a difference in kind. The modulus is
already huge compared to the key you end up using
it for, so only reaching half the group isn't a
problem. But you shouldn't leak even trivial
information.

Greg.

--
From: Tom St Denis on 13 May 2010 10:50
On May 13, 10:28 am, g...(a)nope.ucsd.edu (Greg Rose) wrote:
> In article <20100513063338.0ed9a...(a)tritium.streitmacht.eu>,
> Ertugrul Söylemez  <e...(a)ertes.de> wrote:
>
>
>
>
>
> >g...(a)nope.ucsd.edu (Greg Rose) wrote:
>
> >> In article
> ><d5be07db-9929-4c15-8415-f0185fea3...(a)e34g2000pra.googlegroups.com>,
> >> Bryan  <bryanjugglercryptograp...(a)yahoo.com> wrote:
> >> >Ertugrul Söylemez wrote:
> >> >> In general, it's considered best to pick the largest subgroup.
>
> >> > No, currently practice is to pick a base that generates a subgroup
> >> > of large prime order. When the modulus is safe prime 'p',
> >> > cryptographers tend to choose a base that generates a subgroup of
> >> > prime order q=(p-1)/ 2. That said, I don't know of any security
> >> > problem with your advice to pick a safe prime and a generator of the
> >> > entire group.
>
> >> I guess it depends what you want to do with the answer, and I don't
> >> think the OP actually said. If it is for Diffie-Hellman, though, there
> >> is a reason to prefer using the prime-order subgroup.  Note that it's
> >> straightforward to figure out which subgroups a group element is in,
> >> and that for a safe prime the order q subgroup is exactly elements
> >> that are squares. Suppose you use a generator of the entire group, in
> >> general. Alice intentionally chooses a square, and does D-H with
> >> Bob. Now if the result of the D-H is a square, Alice knows that Bob
> >> chose a square too; otherwise he didn't. This is one bit of
> >> information that Alice shouldn't have, and can't be concealed.  Worse,
> >> if the D-H is in the clear, anyone can tell that one bit of
> >> information about both Alice and Bob's choices.
>
> >> [...]
>
> >> Basically, it's always safest to use the
> >> large-prime-order subgroup in this and most other
> >> contexts.
>
> >I already noted that a modulus of b bits gives a strength of b - 1 bits
> >effectively, so I took that into account.  You lose that bit, no matter
> >what you do.  If you use the prime order subgroup, you reach only half
> >of all elements.  If you use the full group, the above attack is
> >applicable.
>
> I think it's a difference in kind. The modulus is
> already huge compared to the key you end up using
> it for, so only reaching half the group isn't a
> problem. But you shouldn't leak even trivial
> information.

To restate what Greg has been saying, basically it's better to have
one large prime order group Q than an even larger composite order
group Q' if the factors of #Q' are smaller than #Q.

Which is why, for example, you don't want a generator that makes the
group of order p-1 modulo p since p being prime means p-1 has at least
one 2 as a factor.

Tom
From: Bryan on 13 May 2010 20:01
Ertugrul Söylemez wrote:
> I already noted that a modulus of b bits gives a strength of b - 1 bits
> effectively, so I took that into account.

I'm sorry I missed where you noted that because I certainly would have
challenged it. If measuring strength in bits means anything, it means
breaking a system with a strength of b bits takes a work factor of
2**b. We know that is not the case with the one-way-function at issue
here. Integer discrete log is sub-exponential. Even in groups where
the best attack known is exponential-time, there is a general square-
root attack so the exponent is b/2.

> You lose that bit, no matter
> what you do.  If you use the prime order subgroup, you reach only half
> of all elements.  If you use the full group, the above attack is
> applicable.

I do not see any "above attack". The claim of "a strength of b - 1
bits effectively" suggests you are thinking along the lines of
exhaustive search. But maybe I'm mis-reading you. I've quibbled with a
couple of your previous statements, but I thought you had some
defensible content. Here I just don't see what you are on about.


--
--Bryan Olson
From: Greg Rose on 14 May 2010 00:42
In article <20100514032501.731f1720(a)tritium.streitmacht.eu>,
Ertugrul Söylemez <es(a)ertes.de> wrote:
>Bryan <bryanjugglercryptographer(a)yahoo.com> wrote:
>
>> Ertugrul Söylemez wrote:
>> > I already noted that a modulus of b bits gives a strength of b - 1
>> > bits effectively, so I took that into account.
>>
>> I'm sorry I missed where you noted that because I certainly would have
>> challenged it. If measuring strength in bits means anything, it means
>> breaking a system with a strength of b bits takes a work factor of
>> 2**b. We know that is not the case with the one-way-function at issue
>> here. Integer discrete log is sub-exponential. Even in groups where
>> the best attack known is exponential-time, there is a general square-
>> root attack so the exponent is b/2.
>
>I see. I thought you are referring to the Legendre symbol, which is in
>fact "trivial information" and not very useful. I see that if the base
>b is already a square (b = r^2), then the Legendre symbol doesn't give a
>useful answer, but as far as I see that reduces the strength against
>exhaustive search by one bit and that's it. So how does the attack
>work? I'd be grateful for a pointer or a keyword to search for.

I don't think anyone is talking about exhaustive
search here. I was talking about leaking a bit of
a secret, when it is avoidable.

>
>> > You lose that bit, no matter what you do.  If you use the prime
>> > order subgroup, you reach only half of all elements.  If you use the
>> > full group, the above attack is applicable.
>>
>> I do not see any "above attack". The claim of "a strength of b - 1
>> bits effectively" suggests you are thinking along the lines of
>> exhaustive search. But maybe I'm mis-reading you. I've quibbled with a
>> couple of your previous statements, but I thought you had some
>> defensible content. Here I just don't see what you are on about.
>
>I should have made myself clear. "The above attack" refers to /your/
>post, in which I thought you were referring to the Legendre symbol.

I thought "the above attack" was where I (not
Bryan) pointed out that one bit of the secret key
gets leaked, because of squareness, Legendre
symbols, or quadratic residues, whichever you want
to call it.

Greg.
--
From: Bryan on 14 May 2010 07:08
Ertugrul Söylemez wrote:
> Bryan wrote:
> > Ertugrul Söylemez  wrote:
> > > I already noted that a modulus of b bits gives a strength of b - 1
> > > bits effectively, so I took that into account.
>
> > I'm sorry I missed where you noted that because I certainly would have
> > challenged it. If measuring strength in bits means anything, it means
> > breaking a system with a strength of b bits takes a work factor of
> > 2**b. We know that is not the case with the one-way-function at issue
> > here. Integer discrete log is sub-exponential. Even in groups where
> > the best attack known is exponential-time, there is a general square-
> > root attack so the exponent is b/2.
>
> I see.  I thought you are referring to the Legendre symbol, which is in
> fact "trivial information" and not very useful.  I see that if the base
> b is already a square (b = r^2), then the Legendre symbol doesn't give a
> useful answer, but as far as I see that reduces the strength against
> exhaustive search by one bit and that's it.

Ah -- your previous reply followed-up Greg Rose, who pointed out that
use of base that generates of the entire multiplicative group can leak
whether a secret exponent is odd or even.Greg was responding to my
statement, "I don't know of any security problem with your advice to
pick a safe prime and a generator of the entire group." I don't think
Greg was pitching this issue as major attack, rather as something we
should be aware of, which I was not. A one-bit reduction in strength
against exhaustive search is of no importance.

> So how does the attack
> work?  I'd be grateful for a pointer or a keyword to search for.

I referred to two attacks. The first is to compute the integer
discrete logarithm in sub-exponential time, perhaps using the number
field sieve. The second attack works in any finite cyclic group where
we can efficiently compute the group operation; it is exponential
time, but the exponent is half that of exhaustive search. For search
keywords, try the obvious ones plus -- and this is not a joke -- "wild
kangaroos".


--
--Bryan Olson

First  |  Prev  | 
Pages: 1 2 3
Prev: What do I need to know to design a cryptosystem?
Next: Is this construct a MAC ?