Cryptography-Digest Digest #892, Volume #12 Tue, 10 Oct 00 21:13:01 EDT
Contents:
Re: NSA quote on AES ("Douglas A. Gwyn")
Re: Block Cipher Question ("Douglas A. Gwyn")
Re: A new paper claiming P=NP ("Douglas A. Gwyn")
Re: Rijndael implementations ("Paul Pires")
Re: A new paper claiming P=NP (David A Molnar)
Re: FTL Computation (Wayne Throop)
Re: Microsoft CAPI's PRNG seeding mechanism (Tim Tyler)
Re: A new paper claiming P=NP (Timothy Chow)
Re: Comments on the AES winner ("Douglas A. Gwyn")
Hardware Implementation of DSA (Brian Phillips)
Re: Does Rijndael look Linear or is it just me? (John Savard)
Re: On block encryption processing with intermediate permutations (Bryan Olson)
Modular Exponentiation (Steve Su)
Re: Rijndael implementations (Jim Gillogly)
Re: Rijndael implementations ("Paulo S. L. M. Barreto")
Re: FTL Computation ("Trevor L. Jackson, III")
Re: Rijndael has a very good S-Box ("Paulo S. L. M. Barreto")
----------------------------------------------------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: NSA quote on AES
Date: Tue, 10 Oct 2000 22:10:45 GMT
Greggy wrote:
> > That has already been stated up front by NIST. AES is intended
> > for use to secure sensitive-but-unclassified (SBU) information.
> Well, that settles it for me. I won't be using it for any of
> my "classified" information...
> > An example would be competitive-procurement records.
> But my classified information is like my SS# or credit card number.
> The latter is used for my personal procurement over the internet. So I
> won't be procuring with AES it seems...
You're being silly or obtuse. "Classified" for US governmental
purposes is well defined (and based on potential impact on the
national security). SBU means not having significant impact
on national security, but still needing protection for other
reasons, such as privacy.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Block Cipher Question
Date: Tue, 10 Oct 2000 22:18:55 GMT
musashi_x wrote:
> The end recipient is the only other person who knows that I alter the output
> in this way, ...
No, that is not likely in any system subjected to widespread
use in the real world. (It could be true for a toy system,
but who cares.) The standard assumption (attributed to
Kerchhoff) is that the enemy knows every datil of system
operation except the specific keys (cryptovariables) used.
If a system is not sufficiently secure under such conditions,
then fielding it would be a gamble.
------------------------------
Crossposted-To: comp.theory,sci.math,sci.op-research
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: A new paper claiming P=NP
Date: Tue, 10 Oct 2000 22:24:52 GMT
Bill Unruh wrote:
> Just download the ps file and then use ps2pdf to change it to a pdf
> file.
Or Acrobat Distiller.
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: Rijndael implementations
Date: Tue, 10 Oct 2000 16:20:26 -0700
<snip>
> http://www.btinternet.com/~brian.gladman/cryptography_technology/rijndael/in
> dex.html
>
> where I have just updated my own implementation (in C++). On the 200MHz
> Intel reference platform it offers around 70Mbits/second using large tables
> but other options are provided as well.
Hope you don't mind a dumb question. If a Megabyte is 1024^2 bits (1.048576
million
bytes) as opposed to1 million bytes, is a Mbit 1 million bits or something else?
Paul
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: Re: A new paper claiming P=NP
Date: 10 Oct 2000 23:24:04 GMT
In sci.crypt Jeremy Spinrad <[EMAIL PROTECTED]> wrote:
> By the way, I certainly do not advocate creating a program for every algorithmic
> paper submitted. Proving P = NP is a special case here. Basically, most people
> will not believe that it is true, since too many false claims have been
> disproved, and it behooves an author to do some extra work before the community
> takes it seriously. I know that if I proved P = NP, I would be happy to do an
Out of curiosity, is there a list of famous, but mistaken, "proofs" that
P = or != NP (or other complexity theory results) ? Papadimitriou's book
mentions a mistaken proof that integer linear programming was in P, and a
few months ago I saw a mistaken paper trying to show that NL != NP.
-David
------------------------------
From: [EMAIL PROTECTED] (Wayne Throop)
Crossposted-To: sci.astro,sci.physics.relativity,sci.math
Subject: Re: FTL Computation
Date: Tue, 10 Oct 2000 23:20:26 GMT
: [EMAIL PROTECTED] (David C. Ullrich)
: I've hesitated to ask. But I wonder if anyone can say exactly what
: "faster than light computation" _is_. The speed of light is measured
: in units like meters per second. I don't see how to measure the speed
: of a _computation_ in meters per second...
It's like this. We will presume a simple model of a computation;
a state machine of some sort, with a state change involving a physical
process confined to some volume of space. Now, a stable state of that
physical process can't follow from a prior stable state faster than
light can propogate across the volume. If states sequence faster than
that, the physical process must involve some effect that propogates FTL.
Yes, this description is a bit vague. But that's roughly how a velocity
is related to a speed of computation; there's a famous story (maybe
apocryphal) that Seymour Cray stated that the most serious engineering
challenge in the future of computer hardware design will be the length
of the wires that connect the components. Cray computers were actually
designed to be cylinders so that interconnections could be shortened,
compared to "flatening out" the curve.
But don't be confused. In general, propogation rate of signals in
communicating from point A to point B is not related to the data rate
(bits persecond) of the data received at B.
Note also: lots of progress in computing occurs by making the physical
process asynchronous, so that the physical state of the entire volume of
the CPU doesn't represent a discrete, sequential state. Pipelining,
parallelism, lots of things. But what's going on there is that the
"state machines" are of much smaller volume, and are then connected
together. In this sense, Seymour Cray's prediction comes true.
"Supercomputers" nowdays are composed of vast arrays of very small chips,
and minimizing the need to exchange information between these chips,
and getting them relatively close together is where all the skull sweat
is going... that and packing more and more components into smaller and
smaller volumes inside each chip.
Wayne Throop [EMAIL PROTECTED] http://sheol.org/throopw
"He's not just a Galaxy Ranger... he's a Super-Trooper!"
------------------------------
Crossposted-To: sci.crypt.random-numbers
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Microsoft CAPI's PRNG seeding mechanism
Reply-To: [EMAIL PROTECTED]
Date: Tue, 10 Oct 2000 23:06:50 GMT
In sci.crypt.random-numbers Tim Tyler <[EMAIL PROTECTED]> wrote:
: In sci.crypt.random-numbers Pascal JUNOD <[EMAIL PROTECTED]> wrote:
: : By the way, the seeding mechanism source of sun.security.* Java package
: : is not available, or am I wrong ?
: Apparently, it's in the SecureRandom documentation:
Full source code for the SeedGenerator class is available here:
http://java.fh-wolfenbuettel.de/jdk1.1/src/java/security/SeedGenerator.java
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ ILOVEYOU.
------------------------------
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: Re: A new paper claiming P=NP
From: [EMAIL PROTECTED] (Timothy Chow)
Date: Tue, 10 Oct 2000 23:37:56 GMT
In article <8s08ek$f82$[EMAIL PROTECTED]>,
David A Molnar <[EMAIL PROTECTED]> wrote:
>Out of curiosity, is there a list of famous, but mistaken, "proofs" that
>P = or != NP (or other complexity theory results) ? Papadimitriou's book
>mentions a mistaken proof that integer linear programming was in P, and a
>few months ago I saw a mistaken paper trying to show that NL != NP.
I don't know of a list, but I think Edward Nelson claimed a proof of
P != NP a couple of years ago. He got as far as planning a series of
seminars where he would explain his proof before he found an error and
withdrew the claim. However, I imagine that it's difficult to get a
hold of his preprint, if indeed he ever produced one.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Comments on the AES winner
Date: Tue, 10 Oct 2000 22:52:53 GMT
Future Beacon wrote:
> Does anybody think that the United States Government cannot crack
> this code?
Does anybody think that they can? What is the point of asking
such questions in the absence of the *knowledge* it takes to
answer them?
------------------------------
From: Brian Phillips <[EMAIL PROTECTED]>
Subject: Hardware Implementation of DSA
Date: Tue, 10 Oct 2000 17:04:19 -0700
I was wondering if anyone had run across any hardware implementation of
DSA? I am attempting this right now and can't find much on it.
Any and all help is much appreciated.
Thanks,
Brian
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Does Rijndael look Linear or is it just me?
Date: Tue, 10 Oct 2000 23:49:17 GMT
On Tue, 10 Oct 2000 19:03:43 GMT, Albert Yang <[EMAIL PROTECTED]>
wrote, in part:
>But informal survey, is it just me or does Rijndael look very linear and
>looks to come under some SERIOUS attack from linear crypto attacks in
>the not so distant future?? Especially now that almost 100% of the
>crypto community has only 1 target... I think there is a basis for the
>paranoia, don't you?
Well, an early post of mine soon after it was adopted noted -
mistakenly, I now believe - that the number of rounds in it could have
led to asymmetries making it much weaker than it needed to be for
differential cryptanalysis.
Rijndael would indeed be "linear", or the equivalent of linear in
GF(2^8), if it weren't for the S-boxes. Although the S-boxes are also
based on GF(2^8), which *is* alarming, they appear to be based on it
in a way that is not harmful.
The S-boxes appear to have excellent properties as far as resistance
to differential and linear attacks are concerned.
Of course, maybe they're too good, and something subtler is possible.
Whether the Square attack is part of it, or should be ignored, is
another matter...
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: On block encryption processing with intermediate permutations
Date: Wed, 11 Oct 2000 00:11:13 GMT
Mok-Kong Shen wrote:
> Bryan Olson wrote:
[...]
> > I don't see how it could possibly be unclear what scheme
> > my attack applies to. The modified scheme is not relevant
> > to the questions at issue.
>
> Since I proposed my scheme, I naturally want it to be
> useful, i.e. not being cracked. So, since you told the
> way that prevents your attack to function, I modify it
> accordingly so that it is immune to it. Why not, since
> the modification is trivial??
It only addresses the particular exploit, not the defect.
> > > So through this trivial modification (simply leaving out
> > > one inter-round permutation, while maintaining the other
> > > inter-round permutations as before) my scheme becomes
> > > immune to your attack according to what is quoted from
> > > you above exactly. Do you have anything to say to that
> > > now??
> >
> > The FAQ says it well:
> >
> > If you don't have enough experience, then most likely
> > any experts who look at your system will be able to find
> > a flaw. If this happens, it's your responsibility to
> > consider the flaw and learn from it, rather than just
> > add one more layer of complication and come back for
> > another round.
>
> It suffices for me that you apparently don't have anything
> to say to what I wrote above now.
The quote from the FAQ says something important.
--Bryan
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Steve Su <[EMAIL PROTECTED]>
Crossposted-To: comp.arch.fpga,comp.lang.vhdl
Subject: Modular Exponentiation
Date: Tue, 10 Oct 2000 14:28:43 -1000
I'm trying to implement modular exponentiation on an FPGA (specifically
targetting a Xilinx Virtex V300) as part of a hardware implementation of
a public-key encryption system. I'm trying to find an area efficient
implementation of modular exponentiation. I've come across several
algorithms which should help make my design more efficient, including the
square-and-multiply and Montgomery's multiplication algorithms.
While both methods seem fairly straight-forward, there are some parts
which aren't too clear to me. This may be because I lack a background in
modular arithmetic.
The thing that I need help with right now is the algorithm for Montgomery
reduction of an integer. The algorithm I've found is:
Given a prime M, and a radix R > M, m = bit-length of M
MRED(T), T < RM, R=2^m, gcd(M,R) = 1
U = TM' mod R
t = (T + UM) / R
IF t >= M RETURN t - M
ELSE RETURN t
t = TR' mod M
One of the conditions for the reduction is that:
RR' - MM' = 1
What I want to know is, where does M' and R' come from? (i.e. How do I
calculate M' and R'?) I've also noticed that some papers use R' while
others use the notation R^-1. Is there a difference?
I've tried looking at the Montgomery's paper, "Modular Multiplication
without Trial Division" as well as other papers on Montgomery
multiplication, but I haven't found anything particularly helpful.
Also, is the use of Montgomery multiplication and the square and multiply
algorithm the best (resource-wise) approach to use when attempting to
implement modular exponentiation in hardware?
If anyone could provide with some help on this, I would really appreciate
it. Seeing someone's VHDL implementation would be nice, but I really want
a good grasp of the fundamentals rather than just to copy code. If anyone
could recommend any good resources (books, websites, papers, etc) on this
stuff, that would be a great help.
If you could e-mail any responses to me that would be terrific. Thanks in
advance.
-Steve
[EMAIL PROTECTED]
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: Rijndael implementations
Date: Wed, 11 Oct 2000 00:41:16 +0000
Paul Pires wrote:
>
> <snip>
> > http://www.btinternet.com/~brian.gladman/cryptography_technology/rijndael/in
> > dex.html
> >
> > where I have just updated my own implementation (in C++). On the 200MHz
> > Intel reference platform it offers around 70Mbits/second using large tables
> > but other options are provided as well.
>
> Hope you don't mind a dumb question. If a Megabyte is 1024^2 bits (1.048576
> million
> bytes) as opposed to1 million bytes, is a Mbit 1 million bits or something else?
Yes, 1 Mbit or Mb is 2^20 bits to an engineer. To a marketer it may be 10^6 bits,
just as a MB may be 10^6 bytes, depending on what they need for their marketing
campaign.
70Mbits/sec is an excellent speed for a block cipher in software on a 200MHz
PPro. Network throughput is usually measured in bits/s, and storage is usually
measured in bytes.
--
Jim Gillogly
Mersday, 20 Winterfilth S.R. 2000, 00:35
12.19.7.11.4, 7 Kan 7 Yax, Eighth Lord of Night
------------------------------
Date: Tue, 10 Oct 2000 22:41:07 -0200
From: "Paulo S. L. M. Barreto" <[EMAIL PROTECTED]>
Subject: Re: Rijndael implementations
Brian Gladman wrote:
>
> "lcs Mixmaster Remailer" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > What is the intellectual property status of the Rijndael
> > implementations at the NIST web site?
> >
> > http://csrc.nist.gov/encryption/aes/round2/r2algs-code.html#Rijndael
> >
> > It is known that the algorithm itself is public domain, but what about
> > the implementations (a separate issue)? Is this source code free for
> > commercial use?
> >
> > Names appearing on the C implementations include Paulo Barreto, Antoon
> > Bosselaers & Vincent Rijmen. There is no IP statement in the source
> > files; no claim of copyright, no explicit release to the public domain.
> >
> > Rijmen is of course one of the creators of Rijndael, and his staements
> > may have publicly disclaimed his rights, but what about the others?
Please read the newest available code (version 2.4). The sources are
explicitly put in the public domain. BTW, version 3.0 is forthcoming.
Best wishes,
Paulo Barreto.
------------------------------
Date: Tue, 10 Oct 2000 20:57:49 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Crossposted-To: sci.astro,sci.physics.relativity,sci.math
Subject: Re: FTL Computation
Paul Lutus wrote:
> That is how it is a mixing of terms. But it can get worse -- the OP made an
> argument that relied on smoke, not physics. In a manner of speaking he said
> that, if he transmitted the word "dictionary," and if the receiver knew how
> to translate that token into an actual dictionary, the result would exceed
> the original communication channel's capacity, therefore presto -- FTL!
This is incorrect because the amount of information transmitted does not depend
upon the later translation process. If one translates the signal to the pocket
version of Webster's Abridged one gets a different result that if the
translation produces the 20-volume Unabriged OED. The information transmitted
is calculated from the space of possible message from which the signal
"dictionary" was chosen. The rest is irrelevant smoke and mirrors.
------------------------------
Date: Tue, 10 Oct 2000 23:02:39 -0200
From: "Paulo S. L. M. Barreto" <[EMAIL PROTECTED]>
Subject: Re: Rijndael has a very good S-Box
Tom St Denis wrote:
>
> I am replying to all three of your posts...
>
> In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] (John Savard) wrote:
> > Using a small BASIC program, I searched for differential
> > characteristics, and linear (well, affine? over GF(2^8), anyhow)
> > approximations to the S-box.
>
> An affine linear approximation is something like y = a xor b xor 1.
>
> > The differential behavior of the Rijndael S-box is simply astounding.
>
> Dude check out my website, I have code that makes "good" sboxes of
> various sizes (odd or even bit sizes). The sbox is based on
> multiplicative inversion in a GF. It was used by Matsui in Misty and
> by Tom St Denis in TC5.
>
> > If you consider S(i) xor S(i xor diff), for all 256 values of i, this
> > expression will often take on a value zero or two times instead of
> > once, as is ideal...and may take on one value _four_ times.
> >
> > That's as strong as any differential characteristic of the S-box gets.
>
> Technically there are 255 '4' in the xor-pair table and the rest is
> zeros and twos. That's not the best an sbox could be in theory though.
Yes, it is. The differential uniformity of an S-box is determined by
the maximal entry in its difference table, and over GF(2^8) there will
*always* be at least one '4' entry there. Whether there are 255 or any
other count of occurrences of '4' is irrelevant for a byte-oriented
cipher like Rijndael.
> > As for linear approximations, things are a bit better for the
> > cryptanalyst, but not by much.
> >
> > S(i) is equal to a*i xor b (where the multiplication is done in
> > GF(2^8)) as many as 13 times out of 256, where a=23 and b=163.
> >
> > The second best linear approximation *also* occurs for a=23, this time
> > with b=56; this one is true 11 times.
> >
> > For a=1 and a=23, there are multiple "approximations" that show up,
> > and most commonly they are true around 8 times.
> >
> > The approximation a=147 and b=99 is true 9 times, and the only other
> > value of b that gives an approximation true more than 4 times is 229,
> > with a=147 b=229 true 5 times, so this approximation may have less of
> > a "noise level" to contend with.
> >
> > On the other hand, if the multiple approximations at either a=1 or
> > a=23 can be made to work together, to provide a strong linear
> > approximation - but with _partial information_, something might be
> > done.
>
> All linear approximations are biased (affine/linear) by at most 16
> times. So given for example (y0 = x0 xor x1 xor x7) that will hold in
> the sbox for at most 112/256 or 144/256 times. When the approximation
> deviates from 128/256 times it can be exploited.
The linear behaviour of the x^{-1} mapping over GF(2^8) is optimal, as
is the differential behaviour.
> Of course the inverse sbox has the same low xor-pair, all you did is
> transpose the xor-pair matrix!
>
> In the case of Rijndael an affine transform is applied after the sbox
> lookup to help muddle the low non-linear order of the output.
What do you mean by "non-linear order"? Your usage of this expression
is certainly nonstandard. Rijndael's S-box has maximal nonlinear order
(namely, 7). Check the Handboook of Applied Cryptography for details on
this concept.
The affine transform is applied to prevent interpolation attacks, which
-- in the case of the x^{-1} mapping -- are not based on this mapping's
nonlinear order but rather on its algebraic simplicity (the polynomial
expansion has a single term; after the affine transform it has nine).
Best wishes,
Paulo Barreto.
------------------------------
** 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
******************************
