Cryptography-Digest Digest #741, Volume #11 Tue, 9 May 00 12:13:01 EDT
Contents:
Re: F function. (Mark Wooding)
Re: AEES Advanced ("ink")
Re: PlatyMAC a new Message Authentication Code. (David A. Wagner)
Re: Why no civilian GPS anti-spoofing? / proposal (Dave Ashley)
Re: F function. (David A. Wagner)
Re: F function. (David A. Wagner)
Re: F function. ([EMAIL PROTECTED])
Re: F function. ([EMAIL PROTECTED])
Re: Any good attorneys? (Padgett 0sirius)
Re: Prime Generation in C,C++ or Java ([EMAIL PROTECTED])
Re: An argument for multiple AES winners ("Scott Fluhrer")
Re: RSA ([EMAIL PROTECTED])
Re: Encryption code or addons for VB? ([EMAIL PROTECTED])
Re: Prime Generation in C,C++ or Java ("Axel Lindholm")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: F function.
Date: 9 May 2000 14:55:03 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
>
> Simon Johnson wrote:
> >
> > This is a petty little F-Function. I am almost certain this is easily
> > breakable.
> >
> > Here it is anyway:
> >
> > y=(x+k) ^ 3 mod 256
> >
> > X = some data, K = sub-key. (Function designed for Fiestel)
>
> That's not a function of the input since x^3 mod p (p = composite) is
> not bijective. So it most likely has very bad characteristics.
My initial objection would be that it's a bit narrow for a Feistel
function, unless you're using a Skipjack-like mini-Feistel cipher as a
16x16 S-box.
However, something similar might make a reasonable S-box. Let me think.
Briefly borrowing an idea from IDEA (;-)), let s(x) = x^9 mod 257. This
is clearly an invertible function, since s(x)^57 = x (mod 257). s(256)
= 256, so that's not an issue. There are some undesirable properties,
though. In particular, s(0) = 0 and s(1) = 1.
This can be fixed by using S0(x) = s((x + 22) mod 256). Why did I
choose 22? Well, I tried all possible additive constants, and 22 seemed
to have (joint) best differential characteristics. The most probable
characteristic has probability 14/256, which isn't marvellous, but
iterated 16 times is (just) good enough to be beyond reach. I've not
investigated linear characteristics. If someone else wants to try that,
that'd be cool.
As to using this thing in a block cipher, I'd consider putting four of
these things in a row, with different exponents and additive constants,
and following by a good linear mixing step; matrix multiplication over
GF(2^8) seems to be popular. Obviously, in a real application, you
precompute the S functions and their results through the matrix and just
XOR the answers. This then looks a bit *fish-like, I know.
-- [mdw]
------------------------------
From: "ink" <[EMAIL PROTECTED]>
Subject: Re: AEES Advanced
Date: Tue, 9 May 2000 17:03:28 +0200
<[EMAIL PROTECTED]> wrote
>
> Kurt wrote:
> #IMHO it is a bad thing to develop a software that runs slowly
> #in comparison to existing software,
>
> I should answer that there is no 'existing software' for this
> architecture concerning statement above. So Kurt's statement is too
> abstract and my answer was not clear enough. A propos performance of
> AEES-advanced excluding I/O operations is not too bad (1600 Kb/sec).
I beg to differ. We're talking about encryption software in this
newsgroup, and I happily placed your software into that group.
And, no offence intended, your software /is/ slow if compared
to the throughput of any of the AES contestants or - if you don't
like them - DES.
To get an idea of what I mean by performance, I suggest you refer
to the paper "A Performance Comparison of the Five AES Finalists"
by Bruce Schneier and Dough Whiting, available from the
Counterpane web site.
Hope this helps
Regards
Kurt
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: PlatyMAC a new Message Authentication Code.
Date: 9 May 2000 07:44:05 -0700
First, let me see if I understood the MAC:
The i-th compression function f_i : GF(2)^256 -> GF(2)^128
is chosen as a random affine function using 256*128 + 128 bits
of output from a pseudorandom generator.
i.e., f_i(x) := M.x + b where M is a random 128x256 matrix and
b is a random 128-bit vector.
The PRG is initialized with the XOR of the key and an IV, and
we use Merkle-Damgaard hashing to build a MAC out of the f_i's.
Right?
Ok, here are some observations.
If we replace the PRG output by a sequence of truly random bits,
each f_i then becomes a 2-universal hash function [1]. Also, the
Merkle-Damgaard hash of a series of independently-keyed 2-universal
hash functions is itself a 2-universal hash function. (Checking
these claims is left as an exercise for the reader.)
Consequently, we may view this MAC as follows:
Pick h : GF(2)^n -> GF(2)^128 from a family of 2-universal hash
functions, using PRG(key xor IV) for the random choices.
Then the MAC is h(P).
Looking good so far...
Now we run into a problem. G(key xor IV) is not guaranteed to
have any good properties if we assume only that G is a PRG.
For instance, consider G_bad defined by G_bad(x) := S(t(x))
where S() represents a secure stream cipher (e.g., RC4 or 3DES-OFB)
and where t() is the function that drops the high byte of its
input. Clearly this G_bad is a secure PRG if S is; and yet,
G_bad(key xor IV) = G_bad(key xor IV') if IV and IV' differ in
only their high byte, so if you use G_bad, it will be possible
to break the MAC with chosen-IV attacks. Consequently, the
assumption that G is a pseudorandom generator is not enough:
chosen-IV attacks may still allow the adversary to break the
MAC if you are unlucky with your choice of G.
The solution is that we should use a pseudorandom function
(a PRF) F : Keys x IVectors -> {0,1}^*. We could then replace
G(key xor IV) with F(key,IV), and the result will be secure.
Note that if you only have a PRF F' with a short output, then
along with a PRG G you can build a PRF with a long output,
like this: define F as F(k,x) := G(F'(k,x)).
Ok, so back to your scheme. I believe one can prove that, with
this modification, your scheme is secure under two assumptions:
(1) you never re-use an IV, and (2) F is indeed a secure PRF.
This would show that, with this modification, noone will be able
to do better than a birthday attack, i.e., your money is safe! :-)
(Actually, I believe the security of the scheme is a bit better
than that, since I think it's ok if you re-use an IV once, so
long as you don't re-use it twice. But I'll save these details
for a paper I'm in the middle of writing...)
Question: How efficient is this MAC in practice?
[1] Definition: We say that f : Coins x {0,1}^u -> {0,1}^v is
a 2-universal hash function if for all w,x,y,z with w != x
we have Pr_c[f(c,w)=y and f(c,x)=z] = 1/2^v, where the
probability is taken over a random choice of c from the
set Coins. (I hope I got that right; this is from memory.)
------------------------------
From: Dave Ashley <[EMAIL PROTECTED]>
Subject: Re: Why no civilian GPS anti-spoofing? / proposal
Date: Tue, 09 May 2000 15:20:23 GMT
Trevor,
You've clearly given the issue some thought, which worries me even
more. My brief to the FBI will include your name.
Just kidding, of course.
It is interesting dealing with engineering types (as I am myself)
because often we discuss technical challenges like this in engineering
terms, and we don't feel safe because we know that most of the security
precautions taken to protect the public are not adequate.
For example, the other day I was at the airport, and I had a 2-cell
Maglite which was presumably x-ray opaque, and they verified it by
asking me to turn the flashlight on. Ouch! One little lithium battery
in there to make the flashlight work, and the rest of the space is free
for explosive materials or whatever. Does not make me feel safe as an
airline passenger when John Q. Engineer could smuggle a bomb aboard.
In another incident, I was in a McDonald's with engineering students,
and one of them discussed how easy it would be to wipe out the
McDonald's with a pistol. I indicated that it was not so easy, because
after the first shot, people start running. He then pondered at length
the problem of how one would get everyone in the McDonald's, given the
human tendency to avoid being shot.
If he had been an art history student, I would have called the cops
immediately. But, coming from an engineer or mathematician, these types
of game theory questions are quite normal.
So, Trevor, I won't report you to the FBI this time. Unless you are an
art historian.
Dave.
In article <[EMAIL PROTECTED]>,
"Trevor L. Jackson, III" <[EMAIL PROTECTED]> wrote:
> The problem of spoofing correction signals has appeared before,
notably in the
> context of the correction signals broadcast for harbor navigation.
The
> signals are emitted by fixed base stations that know their own
location to
> very high precision ;-), and thus can deduce the error in the GPS
signal in
> real time. They simply broadcast the differential using lower power
(~10 mile
> coverage) so that ships near coastlines can navigate around rocks
safely.
>
> The terrorist threat from disrupting marine navigation does not
provide as
> much human interest as an airliner filled with people, but it offers a
greater
> threat. An LNG tanker contains a serious amount of energy. Running
one a
> ground in a harbor like Boston or Baltimore would threaten a loss of
life
> several orders of magnitude larger than the airliner scenario.
>
> Dave Ashley wrote:
>
> > You bums on this newsgroup are really beginning to worry me. One of
> > you is probably building a transmitter right now and waiting for a
zero-
> > visibility day at the airport.
> >
> > Sick puppies!
> >
> > I'm worried.
> >
> > Dave.
> >
> > In article <8f7u5e$pdr$[EMAIL PROTECTED]>,
> > zapzing <[EMAIL PROTECTED]> wrote:
> > > In article <lOsR4.7372$[EMAIL PROTECTED]>,
> > > [EMAIL PROTECTED] wrote:
> > > > Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
> > > > > Nobody said that. A few state-backed terrorists steering a
> > > > > few jumbo commercial airliners way off course would certainly
> > > > > be sufficient to terrorize the public.
> > > >
> > > > I think my problem with the whole scenario is two-fold. First,
I'm
> > > > basically as anti-gps as you can get. Having firsthand
experience
> > > > using it, I find it of very limited use as an _aid to
> > > > navigation_. That's not to say it's a bad idea, or a waste of
money,
> > > > just that it's primarily useful for doublechecking your current
> > > > location.
> > >
> > > But it could be better.
> > >
> > > >
> > > > Second, it just seems obvious to me that a state sponsored
terrorist
> > > > would have many cheaper/easier ways to terrorise air traffic
than
> > > > this.
> > > >
> > >
> > > Easier, perhaps, but cheaper? all they would need is
> > > a transmitter.
> > >
> > > > When you talk about sending planes off course though, the
thought
> > > > occours to me that while causing planes to collide is
farfetched, it
> > > > may be somewhat easier to keep one lost over the ocean long
enough
> > to
> > > > run out of fuel, or some other navigational shenanegin.
> > >
> > > Such as causing a plane to fly into a mountainside.
> > > Yikes. We certainly don't want that to happen.
> > > Why won't the fedgov let us have the anti-spoofing
> > > signals to prevent such a catastrophie?
> > > I think they *like* it when catastrophies happen,
> > > so they can blame it on terrorists and then grab more
> > > power from a terrified public.
> > > >
> > > > > The fact is, our technological infrastructure is exceedingly
> > > > > fragile, a fact that has many people concerned (and
occasionally
> > > > > somebody actually working on the problem). The more one puts
> > > > > his eggs all in one basket, especially a fragile one, the more
> > > > > likely a catastrophe will occur.
> > > >
> > > > Well, as I said above, you should _not_ be putting your eggs all
in
> > > > the gps basket. Given that the navigator should still be
navigating
> > by
> > > > hand, large deviations from the GPS fix will be obvious. The
> > challenge
> > > > then is to figure out which location is correct. Anywhere inside
> > most
> > > > nations air space this should be trivial, over blue water it's
> > > > probably slightly more problematical.
> > > >
> > > > > The sad thing is that GPS is a nearly ideal application for
> > > > > public-key cryptography (everybody could decode, but only the
> > > > > system itself could encode), which would have solved the
> > > > > spoofing problem.
> > > >
> > > > I don't know, my experience with gps is limited to little black
> > boxes
> > > > that I plugged into other little boxes. ;) I would think though,
> > that
> > > > there would always be at least an impractical spoofing
> > > > attack. Assuming somehow the system sent a signal that everyone
> > could
> > > > decode, which only it could generate. Then, if I wanted you to
think
> > > > you were at point B rather than point A, why couldn't I go to B
and
> > > > transmit the signal to you? Assuming the points were close
enough
> > that
> > > > you didn't notice the time difference, your equipment would
assume
> > it
> > > > was at B.
> > > >
> > >
> > > simply include the current time in the signature,
> > > and put clocks in the little black boxes.
> > >
> > > > --
> > > > Matt Gauthier <[EMAIL PROTECTED]>
> > > >
> > >
> > > --
> > > Do as thou thinkest best.
> > >
> > > Sent via Deja.com http://www.deja.com/
> > > Before you buy.
> > >
> >
> > --
> > -------------------------------------------------
> > Dave Ashley, [EMAIL PROTECTED]
> >
> > Sent via Deja.com http://www.deja.com/
> > Before you buy.
>
>
--
=================================================
Dave Ashley, [EMAIL PROTECTED]
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: F function.
Date: 9 May 2000 07:53:52 -0700
In article <8f7clk$roc$[EMAIL PROTECTED]>,
Simon Johnson <[EMAIL PROTECTED]> wrote:
> This is a petty little F-Function. I am almost certain this is easily
> breakable. Here it is anyway: y=(x+k) ^ 3 mod 256 [...]
Well, the least significant bits don't look so good:
with probability 1/2, all three low bits are zero.
Also, its differential properties are not so good.
The differentials 128 --> 0 and 64 --> 0 hold with
prob. 1/2; 32 --> 0 and 16 --> 0 have prob. 1/4; etc.
And it might be a little slow, because it requires
two multiplications.
Your comments on finding the inverse of the function
seem to contain some confusions. First, it is not
bijective, so there isn't an inverse; second, you
seem to be mis-applying the Euclidean algorithm.
Also, the integers mod 256 do not form a finite field.
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: F function.
Date: 9 May 2000 07:58:24 -0700
In article <[EMAIL PROTECTED]>,
Tom St Denis <[EMAIL PROTECTED]> wrote:
> That's not a function of the input since x^3 mod p (p = composite) is
> not bijective. So it most likely has very bad characteristics.
The first sentence is a non-sequiter: there exist non-bijective functions.
The second seems spot on: non-bijectivity often allows good differentials.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: F function.
Date: Tue, 09 May 2000 15:35:40 GMT
In article <[EMAIL PROTECTED]>,
Tom St Denis <[EMAIL PROTECTED]> wrote:
>
>
> Simon Johnson wrote:
> >
> > This is a petty little F-Function. I am almost certain this is
easily
> > breakable.
> >
> > Here it is anyway:
> >
> > y=(x+k) ^ 3 mod 256
> >
> > X = some data, K = sub-key. (Function designed for Fiestel)
>
> That's not a function of the input since x^3 mod p (p = composite) is
> not bijective. So it most likely has very bad characteristics.
>
Two questions, What does 'bijective' mean?
(Prolly linked to previous) - Why does it matter if P is composite?
Simon Johnson - Speaking Via Deja
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: F function.
Date: Tue, 09 May 2000 15:35:13 GMT
In article <[EMAIL PROTECTED]>,
Tom St Denis <[EMAIL PROTECTED]> wrote:
>
>
> Simon Johnson wrote:
> >
> > This is a petty little F-Function. I am almost certain this is
easily
> > breakable.
> >
> > Here it is anyway:
> >
> > y=(x+k) ^ 3 mod 256
> >
> > X = some data, K = sub-key. (Function designed for Fiestel)
>
> That's not a function of the input since x^3 mod p (p = composite) is
> not bijective. So it most likely has very bad characteristics.
>
Two questions, What does 'bijective' mean?
(Prolly linked to previous) - Why does it matter if P is composite?
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Padgett 0sirius)
Subject: Re: Any good attorneys?
Date: Tue, 9 May 2000 09:09:06
Patent office exists in its own world (not this one). Used to be that one
requirement for issuance was a working model, evidently this is no longer
true as there is one on file at the moment that refers to a FTL device
(US06025810).
Algorithm covered by RSA patent (like Diffie-Helman) was developed under a
government grant at MIT (DH was at Stanford) and both have specific
exclusions. AFAIR (IANAL) the only effective restriction was for commercial
use (not private or government). However since D-H expired some time ago and
RSA expires this year (Sept 15th ?) the question is nearly moot.
I do expect an explosion in commercial offerings that can handle multiple
mechanisms (primarily S/MIME v2 & v3 plus OpenPGP) once RSA does expire.
Personally believe that patents rarely enrich the inventors and do more to
hold back technological development than anything else. 17/20 years is just
too long in modern times but what do I know ?
A. Padgett Peterson, P.E. CISSP: Cybernetic Psychophysicist
http://www.freivald.org/~padgett/index.html
to avoid antispam use mailto:[EMAIL PROTECTED] PGP 6.5 Public Key Available
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Prime Generation in C,C++ or Java
Date: Tue, 09 May 2000 15:52:03 GMT
Bob Silverman <[EMAIL PROTECTED]> wrote:
>> > Is there a quick and relatively short algorithm in any of these
> languages
>> > for generating primes? The primes do not have to be huge, to the
[...]
> The poster said he wanted "5 to 10 digit primes". One does not
> need a probabilistic method. All of the pseudoprimes less than
> 25 * 10^9 with respect to bases 2,3,5,7 have been identified.
> This gives a fast deterministic test. Albeit for 5 digits, trial
> division or table lookup will be faster
While I'll bow out to the correct answer from the expert, I feel
obliged to point out that the short algorithm (in terms of LOC, not
neccesarily speed) in Java is to use
java.lang.BigInteger.isProbablePrime(int certainty). Odds are, of
course, that this is optomized for much larger numbers, but since it's
almost guaranteed to be a native method, may be competative in speed
to a simpler one in bytecodes. It also makes the resultant class file
smaller, which may be an issue if you're transmiting the code.
--
Matt Gauthier <[EMAIL PROTECTED]>
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: An argument for multiple AES winners
Date: Tue, 9 May 2000 08:44:07 -0700
<[EMAIL PROTECTED]> wrote in message
news:8f93g1$1bj$[EMAIL PROTECTED]...
> In article <[EMAIL PROTECTED]>,
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> >
> > [EMAIL PROTECTED] wrote:
> >
> > > Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> > >
> > > > letting
> > > > there to be multiple AES winners is definitely
> > > > a good idea.
> > >
> > > Or pick a candidate that is most unlikely to have patent claims
> (it's
> > > unlikely that Serpent for example would have any relevant patent
> > > claims - it's just too similar to DES).
> > >
> > > Of course, this would also mean totally avoiding algorithms that
> have
> > > obvious potential patent issues (e.g. MARS & RC6).
> >
> > The criteria for the winner are about strength and speed.
>
> And versatility....
And ease of implementation. If you don't think that's important, you try to
implement it in hardware. People who do this stuff for a living tell me
they really don't want to see MARS be AES.
>
> > One cannot
> > speculate on the likelihood of having hidden patent claims. One has
> > to attempt to find these out.
>
> RSA have asserted they have Patents that cover MARS (and RC6)....
RSA's patents on RC6 are irrelevant, as they've already agreed to allow free
use of RC6 if it is selected.
>
> Also, Hitachi has written to NIST claiming that they have patent
> coverage on ideas implemented in all 5 AES candidates apart from
> Rijndael....
Q: Is this new information since the AES3 conference? That is, has Hitachi
given more information since then?
>
> > Actually, I suppose it shouldn't be too
> > difficult for NIST to do the patent search.Further, it is common for
> > government agencies to help one another. NIST could ask the US
> > patent office to cooperate in that task.
>
> They would need to check foreign patents as well. Not such a simple
> task?
Not only that, but you also have to worry about pending patents which (at
least in the US) are confidental. And, the US patent office may be legally
prohibited from cooperating in a search on pending patents.
--
poncho
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: RSA
Date: Tue, 09 May 2000 15:48:56 GMT
Sorry, i think you missed my question, through my badd phrasing.
1.) Does RSA produce an evenly-distrubuted range of output values, (that
looks random, but of course isn't.)?
2.) If this even distrubution caused by the many multiplications which
form the single expondentiation procedure? I'll show what i mean:
y=X^p mod n also equals y= (X*X*X...p....*X) mod n
Sovling for to retrieve X from Y would clearly result in many possible
values, if (p^0(n)-1) mod n = 0. So my idea is, because of this
uncertainty in choosing a correct value, i conclude that the output
should be more 'random' so to speak. I am correct?
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Encryption code or addons for VB?
Date: Tue, 09 May 2000 15:54:30 GMT
Yes there are plenty. www.Softseek.com has a few and download.com should
have a few, though i havn't checked.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Axel Lindholm" <[EMAIL PROTECTED]>
Subject: Re: Prime Generation in C,C++ or Java
Date: Tue, 9 May 2000 18:05:03 +0200
"Lewis-Oakes" <[EMAIL PROTECTED]> wrote in message
news:8f6s6l$cbi$[EMAIL PROTECTED]...
> Is there a quick and relatively short algorithm in any of these languages
> for generating primes? The primes do not have to be huge, to the order of
5
> to ten digits in decimal.
> Thanks
> Justin Lewis-Oakes
>
>
>
One of the most commonly used is the Lucas-Lehmers test. This is a very fast
alg. for testing
if a mersenne number is a prime. A mersenne number is a number built by
subtracting 1 from
2 to the power of p where p is a prime.
The test itself is made by iterating the formula r[k] = (r[k-1]^2 - 2) mod M
where M is the
mersenne number, r[1] = 4 and k => 2. If r[p-1] = 0 where x is any number,
then M is a prime.
Ex: p=5, makes M=2^5-1=31
r[1] = 4
r[2] = (16 - 2) mod 31 = 14
r[3] = (14^2 - 2) mod 31 = 8
r[4] = (8^2 - 2) mod 31 = 0
This means that 31 is a mersenneprime.
Hope this helps you, best regards Axel Lindholm
------------------------------
** 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
******************************
