Cryptography-Digest Digest #293, Volume #14 Fri, 4 May 01 15:13:01 EDT
Contents:
Re: Rijndael Galois Field construction problem. (Walter Hofmann)
Re: Rijndael Galois Field construction problem. ("Tom St Denis")
Re: A Question Regarding Backdoors (Derek Bell)
Re: linear vs nonlinear ("Henrick Hellstr�m")
Re: Random and not random (Matthew Skala)
Re: Random and not random (Matthew Skala)
Re: Random and not random (Matthew Skala)
Re: Message mapping in EC. (Mike Rosing)
Re: Message mapping in EC. (Mike Rosing)
Re: Why Not OTP ? (Bo D�mstedt)
Re: Cryptanalysis Question: Determing The Algorithm? (Bo D�mstedt)
Best encrypting algoritme ("david")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Walter Hofmann)
Subject: Re: Rijndael Galois Field construction problem.
Date: Fri, 4 May 2001 17:58:13 +0200
Reply-To: [EMAIL PROTECTED]
On Fri, 04 May 2001 03:03:47 GMT, jlcooke <[EMAIL PROTECTED]> wrote:
>
>My pardon. 0 is not in a multiplicative group. The trivial element
>was over looked. Let me restate:
> All but the zero element is in the group. Otherwise the GF(2^8) in
>Rijndael wouldn't be reversible.
All elements but 0 of a field are invertible. Thats the definition of a
field.
Walter
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Rijndael Galois Field construction problem.
Date: Fri, 04 May 2001 16:35:31 GMT
"Walter Hofmann" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> On Fri, 04 May 2001 03:03:47 GMT, jlcooke <[EMAIL PROTECTED]>
wrote:
> >
> >My pardon. 0 is not in a multiplicative group. The trivial element
> >was over looked. Let me restate:
> > All but the zero element is in the group. Otherwise the GF(2^8) in
> >Rijndael wouldn't be reversible.
>
> All elements but 0 of a field are invertible. Thats the definition of a
> field.
No that isn't. A field must have all the qualtiies of a ring and also
0. There is a multiplicative identity we shall call 1
1. All elements of the field are units, in other words they have a
multiplicative inverse such that a * a^-1 = 1
And some others...
Note that in Rijndael all elements are invertable including zero. (they say
1/0 = 0)
Tom
------------------------------
From: Derek Bell <[EMAIL PROTECTED]>
Subject: Re: A Question Regarding Backdoors
Date: 4 May 2001 17:49:58 +0100
SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]> wrote:
: The so called open research community could very well be controled
: directly or indirectly what directions the reseach goes.
Or they could be little grey space aliens in disguise...
Derek - Furrfu!!
--
Derek Bell [EMAIL PROTECTED] |"Usenet is a strange place."
WWW: http://www.maths.tcd.ie/~dbell/index.html| - Dennis M Ritchie,
PGP: http://www.maths.tcd.ie/~dbell/key.asc | 29 July 1999.
|
------------------------------
From: "Henrick Hellstr�m" <[EMAIL PROTECTED]>
Subject: Re: linear vs nonlinear
Date: Fri, 4 May 2001 18:55:02 +0200
Yes, it is always possible to find binary operations under which a bijection
F:{0,1}^n -> {0,1}^n is linear in some way. But there are some important
"but"'s:
Suppose that F(x o y) = F(x) o F(y) and that .o. is a group operation, i.e
there is an element e such that for all x we have e o x = x, for all x, y, z
we have x o (y o z) = (x o y) o z, and for each x there is an element x'
such that x o x' = e.
Now, let z be the element such that e = F(z). We have that F(x) = F(x) o e =
F(x) o F(z) = F(x o z). Since F is a bijection this implies that x = x o z,
and hence that e = z is a fixed point for F. Consequently, you only have to
avoid fixed points in the s-boxes to make a group operation o such that F(x
o y) = F(x) o F(y) for all x and y impossible.
You might however always find a group operation o such that F(x + y) = F(x)
o F(y) for all x and y. Simply let o be such that x o y = w iff Ord(x) +
Ord(y) = Ord(w), where Ord(F(x)) = x for all x. (The structure ({0,1}^n,o)
will be isomorphic to the group of integers under addition modulo 2^n.) This
will give you:
F(y) o F(x) =
F(Ord(F(x) o F(y))) =
F(Ord(F(x)) + Ord(F(y))) =
F(x + y).
The biggest "but" of them all is that this will not work over large sets of
keyed functions. While it might be true that F_k(x + y) = F_k(x) o F_k(y),
it will probably not be the case that F_k'(x + y) = F_k'(x) o F_k'(y) where
o is the same operation in both places.
--
Henrick Hellstr�m [EMAIL PROTECTED]
StreamSec HB http://www.streamsec.com
"Tom St Denis" <[EMAIL PROTECTED]> skrev i meddelandet
news:IiwI6.13405$[EMAIL PROTECTED]...
> It's my understanding that a function is only nonlinear wrt to a
particular
> group. For example, DES sboxes are nonlinear wrt to GF(2).
>
> Is it not possible to always define a group in which a function is linear?
> I.e
>
> F(x) o F(x o A) o A = 0 for all A within the group and o is some form of a
> group operator.
>
> For example, F(x) = x + k mod p is nonlinear wrt to GF(2) but if we use
> GF(p) it's linear, etc..
> --
> Tom St Denis
> ---
> http://tomstdenis.home.dhs.org
>
>
------------------------------
From: [EMAIL PROTECTED] (Matthew Skala)
Subject: Re: Random and not random
Date: 4 May 2001 09:32:26 -0700
In article <[EMAIL PROTECTED]>,
John Savard <[EMAIL PROTECTED]> wrote:
>On 3 May 2001 10:46:18 -0700, [EMAIL PROTECTED] (Matthew Skala)
>wrote, in part:
>>It's not good enough for an OTP to be randomly generated. It must be
>>randomly generated *and* independent of the plaintext.
>
>If it isn't independent of the plaintext, it isn't random.
That's not necessarily true. I can certainly define a distribution of
pads that is not independent of the plaintext, and then sample the pad out
of that distibution. You're abosolutely right that that won't have the
perfect security property, but the pad is still "random" in the sense of
being a random variable sampled from *some* distribution.
I can also sample the pad out of a perfect uniform distribution, and then
change the plaintext depending on the pad. Yes, I know that that breaks
the definition of plaintext, since we traditionally assume that the
plaintext is fixed and the cryptosystem just has to deal with it. It was
Mok-Kong Shen's idea to do this, not mine. His dodge is to say that the
plaintext has different segments that can be freely reordered. Anyway, in
such a case the pad is random from a uniform distribution, it doesn't
suddenly change its nature because of the computations I performed
afterwards, but it and the plaintext are not independent. Part of the
trick here is that "independence" is a property of sets of variables, not
of variables themselves.
Over on the other branch of this thread I'm being asked "The bits came out
of a random generator before I changed the plaintext, so how can they not
be random?". I think "They must be independent of the plaintext!" is a
more pedagogically useful response to that than "They're not really
random!" even if both responses are true. We have endless fights here in
sci.crypt about what "random" means. There is a simple definition of
"independent", and I don't think we've ever had a flame war here about
what *that* word means, although it looks like we may be about to have one.
--
Matthew Skala
[EMAIL PROTECTED] "I fish stranger things than you
http://www.islandnet.com/~mskala/ out of my granola every morning."
------------------------------
From: [EMAIL PROTECTED] (Matthew Skala)
Subject: Re: Random and not random
Date: 4 May 2001 09:39:39 -0700
In article <[EMAIL PROTECTED]>,
John Savard <[EMAIL PROTECTED]> wrote:
>No, but somebody knowingly issued a pair of matching constrained OTPs
>that added up to zero. (The constraint would have to be made stricter
I intended that the two constrained OTPs should be generated, issued, and
applied by disjoint sets of people who don't talk to each other except to
hand over the messages - so they don't *know* that the pads matched.
>That's why I think my proposal - first pad constrained, second pad
>unconstrained (and chosen independently when used) - more closely
>meets the needs of the client.
It's much easier to prove perfect secrecy if one of the pads is
unconstrained. But that does mean that the clerk who applies the
unconstrained pad may some day find themselves staring at an all-zero pad
and wondering. You're probably right that that's a better situation,
though, at least if we keep the two-independent-clerks aspect, because in
such a case the clerk is applying an all-zero pad to a message that is
already known to be encrypted with a constrained pad, so the unconstrained
clerk is still not in the position of knowing "I sent a message that was
identical to the original plaintext".
--
Matthew Skala
[EMAIL PROTECTED] "I fish stranger things than you
http://www.islandnet.com/~mskala/ out of my granola every morning."
------------------------------
From: [EMAIL PROTECTED] (Matthew Skala)
Subject: Re: Random and not random
Date: 4 May 2001 10:26:10 -0700
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>some reason for me convenient), (2) I don't look at the
>pad but arbitrary change the order of the messages to K2,
>(3) I look at the pad and based on the information changed
>it to an order K3 which 'by chance' happens to be identical
>to K2. Why is (2) secure and (3) not secure? See also
Scenario (3) does not have the perfect secrecy property, while scenario
(2) does, because in scenario (2) the plaintext and key are independent
and in scenario (3) they are not independent. Independence of plaintext
and key is a requirement for perfect secrecy. That requirement is met in
scenario (2) and not met in scenario (3).
I am boycotting CRC Press because of their legal harassment of Dr. Eric
Weisstein, which you can read about at http://mathworld.wolfram.com/ .
My open letter to them is at http://www.islandnet.com/~mskala/crcpress.txt .
I am therefore loath to recommend a book they publish. However, I have a
copy of Stinson's _Cryptography: Theory and Practice_ which I was given to
use while TA'ing a course where it was the text, and it's a standard
reference on these kinds of topics which you might want to look at in a
library. Independence of random variables is in Definition 2.1 on page
45; perfect secrecy is Definition 2.2 on page 48. Perfect secrecy is
defined as independence of plaintext and ciphertext; from that it is
trivial to derive that independence of plaintext and key is a requirement.
This is not something that's open to debate; it's a theorem. Using some
approximation of Stinson's notation:
For all plaintext x in P, ciphertext y in C, let the key z = x XOR y
which is in K, then:
p_p(x|y) = p_p(x) (perfect secrecy by definition 2.2)
if and only if x and y independent (corrollary 2.2)
if and only if p_c(y|x) = p_c(y) (corrollary 2.2)
if and only if p_k(z|x) = p_k(z) (definition of z above)
if and only if z and x are independent (corrollary 2.2)
Q.E.D.
Corrollary 2.2, for reference, merely states that independence of a and b
is equivalent to p(a|b) = p(b), which is more convenient than the literal
definition of "independence means p(a and b) = p(a)*p(b)".
>I don't yet understand your 'independence' argument. The
>different segments (in fact the different bits) of OTP
>are 'independent' from one another by definition of the
>property of OTP (in contrast, segments of output of a
>PRNG are not entirely independent, there being correlations).
>So suppose the segments are S1, S2, S3 (happen to be
>generated by the source in this order). The corresponding
>messages can be M1, M2, M3 or any of the possible six
>permutations of these. Isn't it that EACH and EVERY of
>the permutations is secure by the theory of OTP 'from
>the very beginning'? If no, why? Suppose the answer is yes.
Let's play poker. I will deal out two poker hands fairly from a
theoretically perfect unbiased shuffled deck, and I will somehow choose
one hand to give to you, and keep one for myself, without looking at them.
Then we each reveal our hands and whoever has the highest-ranking hand
wins. We'll assume that we assign values to suits so as to put a total
ordering on possible poker hands - there's no possibility for the two
hands to be ranked equally. This game is fair, right?
Now, let's play again. I will deal out two hands fairly, just like
before, and then I'll look at them, and choose one to give to you and keep
the other for myself based on what I see. Then we each reveal our hands
and whoever has the highest-ranking hand wins. Do you want to play this
game? Why or why not?
If you were an observer watching me play these two games with someone
else, and you have to, in each case, make a side bet on who will win the
game, assuming I want to win, which game would you prefer to bet on? In
which game is it easier to guess who will win?
The two poker hands in the second game were generated by exactly the same
procedure that you agreed was fair in the first game, and it might occur
that I might make exactly the same choice of which hand to give you, that
I would have made without looking anyway. So by what I think is the same
logic you're trying to apply to the OTPs, the second game should be
perfectly fair, and in both games I should have exactly 0.5 probability of
winning. But if you or anyone else would like to play the second game
with me, I'd be very happy to let you. I'll even give you ten to one
odds. I'm sure we can find a mutually trusted third party here in
sci.crypt to hold the money and generate a randomly-selected permutation
of the 52-card poker deck.
Looking at random selections, and changing your use of them based on what
you see, makes them not random.
--
Matthew Skala
[EMAIL PROTECTED] "I fish stranger things than you
http://www.islandnet.com/~mskala/ out of my granola every morning."
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: Message mapping in EC.
Date: Fri, 04 May 2001 12:39:14 -0500
Cristiano wrote:
> This is still true if the library (I use miracl) does m=m mod p.
> I think that this is bad because the message changes!
m has to be less than p to start with or you can't get it on the curve.
If you're embedding the data and you leave the msb clear, it's going
to be in the range 0<m<p/2, so it's not a problem. You do give
the opponent 1 bit of knowledge, but if your field size is large
enough, it doesn't matter.
Patience, persistence, truth,
Dr. mike
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: Message mapping in EC.
Date: Fri, 04 May 2001 12:47:06 -0500
Doug Kuhlman wrote:
> Seems like they were lucky (and/or more is going on than meets the
> eye). We expect approximately 1/2 of the x values to be on the curve
> (semi-rigorously, due to Hasse-Weil). With 4 "play" bits, you would get
> 16 possible x-values. A priori, we would expect to see about 153 (10
> million / 2^16) "misses".
>
> With five bits, you get 32 possible values for x, which means about 1 in
> 4 trillion values is expected (with no other thought) to "miss" being on
> the curve.
You lost me. If 4 bits is 1/2^2^4 then 5 bits is 1/2^2^5 is 1 in 4 billion.
Or am I missing something?
> I am, of course, assuming that the position of the "play" bits is fixed,
> so that there is no ambiguity on the receiver's end. Allowing for more
> movement of these bits increases the chances of success but seems to
> needlessly complicate the system.
Yeah, they have to be fixed. Using more play bits is better because you can
introduce randomness, but that's a different problem.
> I am quite sure many mathematicians *have* looked at it. And, yes, it
> is quite difficult to prove in practice -- at least as difficult as
> results about densities of primes. There are lots of factors that go
> into trying to rigorously prove that a point exists in every Hamming
> sphere of radius n.
Where would I find references? I've been totally guessing at this, am
not a mathematician, and don't know what keywords to look for. Any mathematicians,
please chime in!
> I do accept the empirical *evidence* that it works, though. There is
> also some sound mathematical reasoning why it should. Proof is a ways
> away, though.
Hey, it worked for the 4 color map :-) In fact, that's kind of how I started
looking at it. I plotted rows of "consecutive" x values to see which half
plane was covered, and seemed to be randomly distributed. After some shifting,
I saw some patterns, but I couldn't correlate them to anything other than
my brain saw "patterns". I doubt I could follow the math, but I'd still be
interested in any published papers.
Patience, persistence, truth,
Dr. mike
------------------------------
From: [EMAIL PROTECTED] (Bo D�mstedt)
Subject: Re: Why Not OTP ?
Reply-To: [EMAIL PROTECTED]
Date: Fri, 04 May 2001 17:14:07 GMT
Frank Gerlach <[EMAIL PROTECTED]> wrote:
> Why is it that people do not like OTP ? It seems that some people do not like
> Public-Key crypto, so why not just exchanging a box of CDs ?
Our HW random number generator produces about one CD/24 hrs,
and I would guess that some of our customers actually use
the SG100 for OTP systems. The simplicity of the system would
also be an advantage in some environments; no technology can
be stolen. Can a CD writer be modified to first read and then
overwrite data ?
Bo D�mstedt
Chief Cryptographer
Protego Information AB
Ideon Gamma Science Park
http://www.protego.se/sg100_en.htm
IDEON dagarna 10-11 maj
http://www.ideon.se/ideondagarna
------------------------------
From: [EMAIL PROTECTED] (Bo D�mstedt)
Subject: Re: Cryptanalysis Question: Determing The Algorithm?
Reply-To: [EMAIL PROTECTED]
Date: Fri, 04 May 2001 17:14:10 GMT
[EMAIL PROTECTED] (pjf) wrote:
> I was giving a talk today about cryptography for my coworkers, and the
> question came up: If someone gets a chunk of cyphertext that they are
> trying to cryptoanalyze, how do they determine what algorithm was
> used, and does that even matter?
Generally, you cannot do that. What you can do is to
sequentially test different assumptions, which may take
longer or shorter time, depending on the target system
and how clever you are at guessing.
Bo D�mstedt
Chief Cryptographer
Protego Information AB
Ideon Gamma Science Park
http://www.protego.se
http://www.ideon.se/ideondagarna
------------------------------
From: "david" <[EMAIL PROTECTED]>
Subject: Best encrypting algoritme
Date: Fri, 4 May 2001 21:01:47 +0200
Hi all.
Im making a backup program, and I don'treally know what is the most secure
algoritme, im using Rijndael rigth now and using 256 bit keys, are rc6
stronger or are there others??
--
Jonathan s
1.33 Tbird Overclok and cpuidmax program.
www.chiptek.org
www.tombstoneblues.com
"Well anyone can be just like me, obviously.
But then, not again, not too many can be like you, fortunately."
Bob Dylan, 'Absolutely Sweet Marie,' 1966
------------------------------
** 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
******************************
