Cryptography-Digest Digest #42, Volume #13 Mon, 30 Oct 00 05:13:00 EST
Contents:
Re: Open Request to Dr. Kaliski, Jr. at RSA Research - looking for your ("John A.
Malley")
Re: how i decode this? (Paul Schlyter)
Re: how i decode this? (Paul Schlyter)
Re: Visual Basic (Paul Schlyter)
Re: how i decode this? (Paul Schlyter)
Re: Decrypt Me (Richard Heathfield)
Re: Q: Computations in a Galois Field (Mok-Kong Shen)
Re: Q: Computations in a Galois Field (Mok-Kong Shen)
Re: BEST BIJECTIVE RIJNDAEL YET? ("Brian Gladman")
XOR based key exchange protocol - flawed? (Mike Connell)
Re: BEST BIJECTIVE RIJNDAEL YET? ("Brian Gladman")
Re: End to end encryption in GSM (Mark Currie)
Re: Psuedo-random number generator (Thomas Pornin)
----------------------------------------------------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: Open Request to Dr. Kaliski, Jr. at RSA Research - looking for your
Date: Sun, 29 Oct 2000 22:04:13 -0800
Albert Yang wrote:
>
> As a service to the newsgroup, I have made Dr. Kaliski aware that there
> is a group of us who would be interested in obtaining his thesis.
>
> Since I work for RSA, I have his email address :-) So if/when I do get
> a copy of it, (pending his permission) I will email you a copy. Sound
> fair?
Yes! Very fair! Thank you for your help, Mr. Yang.
>
> Now, what is the problem in PRNG with elliptic curves you have, as this
> has drawn my interest.
>
It's part of some on-going research that started summer of 2000.
Mok-Kong Shen posted a question in June, 2000 on the premise that
encrypting the output of a predictable (or cryptologically insecure)
PRNG with a secure cipher results in a "practically" secure PRNG output.
I suspected that if the predictable PRNG and the cipher shared
mathematical operations in common it might actually "weaken" the
situation. So I set to work to prove/disprove this "hunch."
One the last day of August, 2000, I posted a URL to a draft paper (to be
submitted to the IEEE Transactions on Information Theory) demonstrating
the encipherment of the output of a predictable linear congruential
generator with ElGamal results in a predictable PRNG even though ElGamal
is a "secure" cipher. The ciphertext-only attack succeeded due to common
mathematical operations between the LCG and ElGamal.
You can download the draft paper if interested at
http://www.homeworlds.com/papers/SECLCG.pdf
And then a (possible) deeper reason for the successful ciphertext-only
attack in that draft struck me - the LCG and ElGamal are of same group,
the multiplicative group Z*p where p is a prime. So does the described
attack generalize? What are the answers to these two questions:
Is any PRNG isomorphic/homomorphic to the multiplicative group Z*p
encrypted by a cipher isomorphic/homomorphic to the same multiplicative
group Z*p always predictable?
AND
Is the output of a predictable PRNG homomorphic to the group G
encrypted by a cipher homomorphic to the same group G always
predictable?
This looked interesting. Prove/disprove this and maybe it can be shown
that encrypting the output of a predictable PRNG homomorphic to a group
G encrypted by a cipher NOT homomorphic to that group always results in
an unpredictable (cryptographically secure) PRNG output - i.e.
encrypting the output of a predictable LCG with a block cipher that's
isomorphic to the Symmetric group S may always be more secure (from this
group point of view).
And maybe this analysis can be extended to cascading ciphers - which is
where I hope to eventually take it.
There is stuff to be learned on my part.
The HAC describes the Generalized ElGamal encryption and lists 7 finite
cyclic groups where the group operation is "easy" to calculate and the
discrete logarithm problem is computationally "hard."
Now one of those groups is the group of points on an elliptic curve over
a finite field.
I'm learning what I can about ECC and PRNG with elliptic curves over a
finite field. Now I'm looking at the encryption of the output of a
predictable LCG with an elliptic curve over a finite field. I'm scouring
the web for papers and thesis on the use of elliptic curves over finite
fields as PRNGs. Fuel for the mental fires.
In particular right now I'm looking at the problem of using the 2D
output of the elliptic curve PRNG as a scalar value - given a sequence
of <x,y> values can one transform the pairs into a scalar value as a
pseudo-random number? Say the elliptic curve over the finite field has
#E(F_p) points on the curve, and that number is prime, I can match these
points one-for-one with the integer values from 1..q where q = #E(F_p).
I could define a relation between those two sets of points (just match
'em up), but I wonder is there's a function to do the same.
I read Sean Hallgren's report at CMU on "Linear Congruential Generators
Over Elliptic Curves" dated May 1994. Mr. Hallgren's approach generated
a sequence of points on a simple elliptic curve and used the discrete
log of that point with respect to some generator G as the scalar output
of the PRNG.
Mr. Hallgren's work pointed me to Dr. Kaliski's work - he reference Dr.
Kaliski's thesis.
So that's where I'm going with this. Gathering more info on the way to
proving/disproving those two questions.
John A. Malley
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: how i decode this?
Date: 30 Oct 2000 07:51:05 +0100
In article <8th81h$f2r$[EMAIL PROTECTED]>,
Simon Johnson <[EMAIL PROTECTED]> wrote:
> In article <8tglmm$fa4$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] (Paul Schlyter) wrote:
>> In article <8teiah$ifv$[EMAIL PROTECTED]>,
>> Simon Johnson <[EMAIL PROTECTED]> wrote:
.........
>>> *LOL*, But on a serious note:
>>>
>>> We can't be expected to even attempt to solve the encrypted cipher
>>> text without knowledge of the algorithm.
>>
>> So you mean it's a good idea to use secret enryption algorithms?
>
> Hell no.
>
> If you write you're own algorithm, publish it. The reasons for this are
> simple. First off, you can determine the _REAL_ security of you're
> algorithm. A little more complex, but equally as valid, If you keep
> you're algorithm secret and an attacker discovers it, this could be a
> problem because you don't know you're security has been compromised.
> Realsing you're algorithm immediatly makes sure that you can not be
> ambushed.
>
> Another reason is more comercial. IF some company tells you they
> have 'Unbreakble encryption', as the often do, and doesn't let u look
> at the algorithm its probably pants. Releasing an algorithm into the
> public allows one to determine if you're product is worth buying.
Doesn't this apply to the military as well? If they reveal
their secret algorithms, then their customers (i.e. the public) can
make a more informed decision on whether they want to pay them
tax money or not..... :-))))
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: pausch at saaf dot se or paul.schlyter at ausys dot se
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: how i decode this?
Date: 30 Oct 2000 07:49:54 +0100
In article <[EMAIL PROTECTED]>,
David Blackman <[EMAIL PROTECTED]> wrote:
> Paul Schlyter wrote:
>
>> In article <8teiah$ifv$[EMAIL PROTECTED]>,
>> Simon Johnson <[EMAIL PROTECTED]> wrote:
>
>>> *LOL*, But on a serious note:
>>>
>>> We can't be expected to even attempt to solve the encrypted cipher text
>>> without knowledge of the algorithm.
>>
>> So you mean it's a good idea to use secret enryption algorithms?
>
> Only if the secret algorithm is at least as good as the well-known
> publicly available ones.
>
> Only if the secret algorithm stays secret. If Blackhat steals one key of
> the day for a well known algorithm, Blackhat gets one day's worth of
> secret information. If Blackhat steals your secret algorithm, you might
> have more of a long term problem.
If the secret algorithm is as good as trusted public algorithm, why
would this be worse than using an algorithm which already is public?
> Only if you don't have to use the algorithm to talk to many people,
> since each person has to be given a copy of something non-standard that
> you can't just download from the net, and after you give them the
> algorithm, they are another potential leak.
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: pausch at saaf dot se or paul.schlyter at ausys dot se
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: Visual Basic
Date: 30 Oct 2000 07:51:40 +0100
In article <PBZK5.190$[EMAIL PROTECTED]>,
Patterson Programming <[EMAIL PROTECTED]> wrote:
> Attribute VB_Name = "BlowfishVB"
..................
> Sub Read_Pi
>
> Pbox(0) = 608135816
> Pbox(1) = -2052912941
> Pbox(2) = 320440878
......... snipped 1032 similar lines ........
> Sbox(3, 248) = -1865090967
> Sbox(3, 249) = -1503863136
> Sbox(3, 250) = 1057563949
> Sbox(3, 251) = -1039604065
> Sbox(3, 252) = -1219600078
> Sbox(3, 253) = -831004069
> Sbox(3, 254) = 1469046755
> Sbox(3, 255) = 985887462
>
> End Sub
Ouch !!!!!!!!!!!!!!!!!!!!!!!!!!
Aren't there any static initialization of arrays in VB?
I guess not... :-(
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: pausch at saaf dot se or paul.schlyter at ausys dot se
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: how i decode this?
Date: 30 Oct 2000 07:50:29 +0100
In article <[EMAIL PROTECTED]>,
Richard Heathfield <[EMAIL PROTECTED]> wrote:
> Paul Schlyter wrote:
>>
>> In article <8teiah$ifv$[EMAIL PROTECTED]>,
>> Simon Johnson <[EMAIL PROTECTED]> wrote:
>>
>>> We can't be expected to even attempt to solve the encrypted cipher text
>>> without knowledge of the algorithm.
>>
>> So you mean it's a good idea to use secret enryption algorithms?
>
> I think there's a difference between using a secret algorithm and using
> an algorithm secretly.
>
> If your algorithm relies on its secrecy for its security, that's a Bad
> Thing, because someone's bound to find out sooner or later if it's
> important enough. But consider this:
>
> Alice has a choice of 50 known, published, well-analysed, robust
> algorithms. She chooses one at random and uses it to encrypt a message.
>
> She sends the message to Bob.
>
> Bob uses their shared secret key on each of the 50 algorithms until he
> hits the right one.
>
> Now, Bob's work (with the key) is O(N) where N is the number of
> algorithms - not an onerous task, whereas Eve's work is incomparably
> vaster than if she knew which algorithm Alice had chosen for this
> particular message.
So then there are 50 algorithms instead of one to try out. This
corresponds to increasing the key size by 6 bits. And in several
years we'll have computers that are some 50 times faster than today's
computers anyway.
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: pausch at saaf dot se or paul.schlyter at ausys dot se
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
Date: Mon, 30 Oct 2000 08:05:02 +0000
From: Richard Heathfield <[EMAIL PROTECTED]>
Subject: Re: Decrypt Me
Chris Nicholson wrote:
>
> Tom St Denis wrote:
>
> > Looks like some convoluted vinegere cipher (sp?)... You should read the
> > HAC (various people have URLs for that...)
> Its along the lines of that, but i dont think its susceptable to the same
> anaylisis to find the key length.
>
I think you'll have to provide a little more ciphertext, perhaps on a
URL, if you want people to crack this. But I suspect that they won't
bother trying, even with more ciphertext, unless you can explain, at the
very least, how it resists the usual attack on Vigenere. Also, an
English description of your algorithm would help your cause.
--
Richard Heathfield
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: Computations in a Galois Field
Date: Mon, 30 Oct 2000 09:08:23 +0100
David Hopwood wrote:
>
> If a cipher designer has chosen to use a field, GF(2^m) is convenient
> because elements are an exact number of bits, and the arithmetic is
> quite efficient.
How does multiplication/division in GF(2^m) compare to Z(2^m)
in computing time for m, say, up to 64 (for average case
of polynomials, without tables, of course)?
>
> > Rijndael uses [0x]11B and Twofish uses 169 - how do one choose the
> > irreducible polynomial ?? Are some better than others ??
>
> The choice of polynomial just changes the representation of the field,
> not its structure. You have to do the analysis for a particular
> polynomial, but other than that, it's fairly arbitrary.
Does this mean that using different polynomials has
consequences in respect of strength of the cipher?
If not, is there is theoretical proof of this fact?
Ton St Denis seems to claim that certain essential
properties of the substitution remain invariant.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: Computations in a Galois Field
Date: Mon, 30 Oct 2000 09:08:32 +0100
Tom St Denis wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
> > I can't remember your post since it is long time back. Do you
> > mean that you showed in the special case of Rijndael that the
> > author's choice is optimal? I presume that's an experimental
> > proof. If yes, then in any other given context one has to
> > do experiments to determine the best polynomial to use with
> > respect to avalanche etc.
>
> No dude, read what I posted. I said "all polynomials" have the same
> sub-optimal diffusion. That's one reason (not the only) for tacking on
> the affine transformation in Rijndael.
>
> This affects other ciphers such as Misty, LOKI97, etc..
I have difficulties to search old posts. Could you say
in one sentence whether you have a theoretical proof of
the above claim or is that a result from experiments?
M. K. Shen
------------------------------
From: "Brian Gladman" <[EMAIL PROTECTED]>
Subject: Re: BEST BIJECTIVE RIJNDAEL YET?
Date: Mon, 30 Oct 2000 08:23:51 -0000
"SCOTT19U.ZIP_GUY" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> [EMAIL PROTECTED] (Brian Gladman) wrote in
> <eN0L5.3659$zO3.111060@stones>:
>
>
> >
> >But in arithmetic coding the original file length does need to be
> >encoded in some way and Matt has a neat way of doing this (and one which
> >I like). But his scheme is just one of many possible ways of encoding
>
> I think you don't know what he did since a length field is not
> use in Matts arithmetic coding.
I did not say there was a length field - I just said that length is encoded
and I do know how he does this.
Brian Gladman
------------------------------
From: Mike Connell <[EMAIL PROTECTED]>
Subject: XOR based key exchange protocol - flawed?
Date: 30 Oct 2000 10:01:01 +0100
Pa, Pb are RSA public keys. (X)Pi means data X encrypted under key Pi.
Xa, Xb are random blocks of data of the same size as the public keys.
1. a -> b : Pa
2. a <- a : Pb
3. a -> b : (Xa)Pb
4. a <- b : (Xb)Pa
Then a and b compute the XOR of Pa,Pb,Xa,Xb. This gives them a
substantional number of shared secret bytes to construct a session key
from.
I have looked at a MITM attack, including substitution of the blocks
in stages 3 and 4, and the replacement of one of the public keys, but
cant see how to make it work. Any ideas?
I couldn't find a mention of anything like this in either Applied
Crypto or Menezes, so it must be very flawed ;) Is there some weakness
in using the public keys in the XOR?
TIA for any comments,
Mike.
--
Mike Connell [EMAIL PROTECTED] +46 (0)31 772 8572
[EMAIL PROTECTED] http://www.flat222.org/mac/ icq: 61435756
------------------------------
From: "Brian Gladman" <[EMAIL PROTECTED]>
Subject: Re: BEST BIJECTIVE RIJNDAEL YET?
Date: Mon, 30 Oct 2000 08:50:07 -0000
"Tim Tyler" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> Brian Gladman <[EMAIL PROTECTED]> wrote:
>
> : if you are going to admit to adjusting your approach to cope with real
> : world constraints, then you cannot reasonably criticise others who do
> : the same in different ways simply because you don't like what they
propose.
>
> Are you talking about something specific?
The point was intended as a general one.
> : At no point have I ever said that I would add information to a file.
Files,
> : as you define them, have a property called length - the number of bits
they
> : contain - and this means that there is no question for them of adding
> : information since it is already there.
>
> If you add the length of the file to the message before encrypting, you
> are adding redundant material to the file. Redundancy in the plaintext
> is best avoided.
I could easily debate this but I won't do so since it is not central to the
issue in question because the ecoding is being done in the compressed file
(I put this bit in only for the sake of completeness)
> : But in arithmetic coding the original file length does need to be
encoded in
> : some way and Matt has a neat way of doing this (and one which I like).
But
> : his scheme is just one of many possible ways of encoding this length
and, so
> : far, you have failed to provide any basis for a claim that this specific
> : approach is better in security terms than any other possible approach to
> : this task [...]
>
> It adds the minimum information (zero bits). Other methods may also get
> down to zero bits. There is no proof that Matt's method is unique
> because it is not.
Which is a part of my point put in another way.
Brian Gladman
------------------------------
Crossposted-To: nl.comp.crypt,alt.comp.opensource,alt.cellular.gsm
Subject: Re: End to end encryption in GSM
From: [EMAIL PROTECTED] (Mark Currie)
Date: 30 Oct 2000 09:19:41 GMT
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
>
>In article <[EMAIL PROTECTED]>,
>[EMAIL PROTECTED] says...
>
>> As other have discussed, this would require heavily modified hardware,
>> and a lot of other things.
>>
>> You are much better and cheaper off buying the product off the shelf.
>> There is a GSM phone with military-class end-to-end encryption
>> available, the Swedish Tiger. Cost is about USD 4000 / handset.
>>
>
>I suspect that the encryption provided is not that secure, i.e. the
>conversation could still be eavesdropped, as the encryption scheme can't
>be that powerful, given the data rate limitations (max. 9.6 or 14
>Kbit/s).
I'm not sure what you mean. How can the data rate limit the strength of the
encryption scheme ?
The main problem that you have is bit error rates. Your encryption scheme must
be able to handle bit errors and synchronisation in cases where bits are lost
(or gained). There are techniques for doing this.
Mark
------------------------------
From: [EMAIL PROTECTED] (Thomas Pornin)
Subject: Re: Psuedo-random number generator
Date: 30 Oct 2000 09:42:07 GMT
According to Brian Wong <[EMAIL PROTECTED]>:
> The decay of an individual atom is a random process; this is a
> necessary consequence of quantum mechanics.
Oh well, quantum mechanics is just a theory. It is not the Truth with a
big T. The physicist faith is that the world can be described as a set
of mostly mathematically expressable laws. We happen to have a set of
such laws, called "quantum mechanics", which works well; in this set,
there is a law that states that some events are unpredictable.
The point is that, as long as quantum mechanics works well, nobody can
prove false this unpredictability, which is just what we need. Anyway,
once we have some "random" bits, we feed them into a pseudo-random
generator, which does not give random bits either, but only a stream of
bits that cannot be distinguished, computationaly speaking, from a true
random unpredictable stream of bits.
Therefore, the point is moot. Maybe, at some time, someone will be able,
using some new theory, to somehow predict the decay of an atom, but
the consequences of such a new theory would be likely to induce some
tremendous progress in the building of computers, thus modifying our
notion of "computationaly secure", which would make the above stated
point even mooter.
--Thomas Pornin
------------------------------
** 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 (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
