Re: An Extremely Simple Public Key Exchange
From: Jim Steuert (pjsteuert_at_rcn.com)
Date: 06/16/03
- Next message: Jim Steuert: "Re: A new public key algorithm based on avalanche properties"
- Previous message: Gerry Myerson: "Re: Beginners Questions on Linear PRNG"
- In reply to: Scott Fluhrer: "Re: An Extremely Simple Public Key Exchange"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Date: Sun, 15 Jun 2003 20:00:45 -0400
Hello Scott,
You are responding to a week-old post. Please look at
the later post with rings2.c, and the points therein.
Here is a more specific answer to your post.
Changing a single bit of any parameter pai will have unpredictable
consequence on the output.
The parameter bits are shared by all other mod 2^k fields of differing
widths
within a layer. Because they share a single set of bits per layer, changing
one
field's parameter will change all parameters for that layer,
in unpredictable ways. And because every output bit is dependent
on all parameters within a layer (due to the homomorphic mixing)
I really don't think that there is a simple answer to your question.
Even if you could change one bit within a layer's, I don't see how you
could
use it to search for changes in other bits, which would change other
parameters.
The total all-layers (and private key) parameter space is much larger
than the number of output bits. It is likely that no amount of changing
(even if you could iterate all the parameter bits on a single layer) would
change the APub value to the desired one.
And dealing with multiple layers is made even more difficult because
of the mixing and multiple ring types.
The code explains everything in detail. However, I do believe that it
deserves a simplified treatment (paper with diagrams) to prove these
points.
-Jim Steuert
On Sat, 14 Jun 2003 12:12:25 -0700, Scott Fluhrer <sfluhrer@ix.netcom.com>
wrote:
>
> "Jim Steuert" <pjsteuert@rcn.com> wrote in message
> news:oprqmgphtddwdye5@news.rcn.com...
>>
>> Hello again,
>> I have coded a fix for the "parameter tweaking" problem
>> that allowed creation of an alternative set of parameters which
>> generate the same APub, and also added three additional ideas:
>>
>> 1. shared parameter bits for multiple fields within the same layer,
>> 2. homomorphic transforms to spread dependencies between bit fields
> within
>> a layer,
>> 3. hash of the common g value along with prior parameters as the only
>> way
>> to create starting field values.
>> 4. non-parameterized final layers for most fields, even though they can
>> get input from other fields.
>>
>> The goal is to make it impossible to create an alternative
>> set of parameters (which are usable with BInv in generating a shared
>> key)
>> given its APub output. I realized that I could not prove this
>> with theory, so here is a concrete example.
>>
>> Working code with a terse explanation is
>> at <"http://users.rcn.com/pjsteuert/rings.c">
>>
>> Please let me know what you think of this.
> Not very much. Here's a hint why not:
>
> - Suppose the attacker selects an arbitrary set of permutations Pa1, Pa2,
> ..., Pa5, and computes Pa5(Pa4(Pa3(Pa2(Pa1(x)))))))) = y.
>
> - Then, suppose the attacker selects one of the Pai's (Pa3, say), and
> flips
> just one of the constant bits it uses to do the addition, turning it into
> Pa3'. Then, the attacker computes Pa5(Pa4(Pa3'(Pa2(Pa1(x)))))))) = z.
>
> Question: how are y and z related? If the attacker flipped the bit that
> was
> added to bit n of the function input, what is the relationship between
> bits
> n-1 through 0 of y and bits n-1 through 0 of z. What is the relationship
> between bit n of y and bit n of z?
>
> Question: how can this observation be used by the attacker to, starting
> at
> an arbitrary set of permutation, quickly change it into a permutation
> that
> generates a specified output?
>
> --
> poncho
>
>
>
-- Using M2, Opera's revolutionary e-mail client: http://www.opera.com/m2/
- Next message: Jim Steuert: "Re: A new public key algorithm based on avalanche properties"
- Previous message: Gerry Myerson: "Re: Beginners Questions on Linear PRNG"
- In reply to: Scott Fluhrer: "Re: An Extremely Simple Public Key Exchange"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
|
