Cryptography-Digest Digest #395, Volume #13 Wed, 27 Dec 00 18:13:01 EST
Contents:
Re: Cryptoanalysis Illegal ??? (JimD)
Re: PRNG (Mok-Kong Shen)
Re: Cryptoanalysis Illegal ??? (Bill Unruh)
Re: Possible AONT? (David Hopwood)
Re: Foolproof Quantum Cryptography (David Hopwood)
Re: Foolproof Quantum Cryptography (David Hopwood)
Re: RSA == hash function? (David Hopwood)
Re: MD5 and hash127 questions ("Joseph Ashwood")
Re: GIF image 1x1 pixels (sic) (wtshaw)
Re: Q: Result of an old thread? (MCKAY john)
Re: polynomial permutation cipher (Bryan Olson)
[rijndael] Efficient hardware S-box implementation (Tim Olson)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (JimD)
Subject: Re: Cryptoanalysis Illegal ???
Reply-To: Jim
Date: Wed, 27 Dec 2000 19:20:59 GMT
On Wed, 27 Dec 2000 09:43:47 +0100, "Jakob Jonsson"
<[EMAIL PROTECTED]> wrote:
>I remember the early 90s, when some vendors made it illegal to break
>encryption algorithms that were part of certain software programs
How can vendors make cryptanalysis illegal? Only governments
can do that.
<(e.g.,
>some word processors). More precisely, when you purchased the software, you
>had to sign a contract disclaiming your rights to cryptanalyze (or
>reverse-engineer) the algorithm or have it cryptanalyzed by someone else. I
>know it didn't prevent people from analyzing and breaking the algorithms
>anyway, but maybe it scared one or two law-abiding potential code crackers
>away.
That still didn't make it illegal. Unwise, possibly, if the vendor
got to hear about it, but not illegal.
You have to get clear the difference between a criminal act and
ligitation by a vendor against a cryptanalyist.
--
______________________________
Posted by Jim Dunnett
dynastic at cwcom.net
nordland at lineone.net
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: PRNG
Date: Wed, 27 Dec 2000 21:20:22 +0100
Cristiano wrote:
>
> "Mok-Kong Shen" <[EMAIL PROTECTED]> wrote:
> > Cristiano wrote:
> > >
> > [snip]
> > > It generate numbers to 32 bits evenly distributed (at least as it seem)
> and
> > > pass all the statistical tests.
> >
> > How do you know that you have applied ALL the statistical
> > tests (that exist)? Have you applied the NIST tests?
>
> Yes. With 10^8 bits.
> Some other idea?
Could you say something about your experience with the
NIST tests? Is the package user-friendly? Could you give
some idea of how well your generator passes the tests?
BTW, your generator is commonly termed (true) RNG, since
PRNG is understood by many to be a deterministic generator.
There used to be experts who commented on generators
based upon physical randomness. Perhaps they are currently
on vacation.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: Cryptoanalysis Illegal ???
Date: 27 Dec 2000 20:26:49 GMT
In <[EMAIL PROTECTED]> [EMAIL PROTECTED] (JimD) writes:
]On Wed, 27 Dec 2000 09:43:47 +0100, "Jakob Jonsson"
]<[EMAIL PROTECTED]> wrote:
]>I remember the early 90s, when some vendors made it illegal to break
]>encryption algorithms that were part of certain software programs
]How can vendors make cryptanalysis illegal? Only governments
]can do that.
They can make it so that if you cryptanalyse their product you violate
an explicit contract you sign with them. They are then entitled to sue
you for breach of contract and demand compensation.
1
]You have to get clear the difference between a criminal act and
]ligitation by a vendor against a cryptanalyist.
"illegal" is often used to apply to both civil and criminal law.
------------------------------
Date: Wed, 27 Dec 2000 20:43:44 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Possible AONT?
=====BEGIN PGP SIGNED MESSAGE=====
Benjamin Goldberg wrote:
> This AONT idea is based very much on the recent thread about order 32
> irreducible GF(2)[x] polynomials.
>
> The security of this is depends on both a 32 bit keyed permutation
> generator, E,
What assumption are you making about E? (Actually it doesn't really
matter because the scheme has weaknesses even if E is a perfect PRP.)
> and a secure hash function, H.
>
> The transform is as follows:
> k = (hash output size) random bytes
> counter = 0
> repeat (filelength/4) times
> do {
> poly = E_k( counter )
> counter = counter + 1;
> } until( irreducible( poly ) );
> crcval = crc( file, poly );
> output( crcval );
> H.add( crcval );
> end repeat
> output( H.result() XOR k );
>
> Reversing the transform is done using CRT.
>
> Any comments?
It is obviously not secure according to the definition of a
computationally-secure AONT in [1] or [2]. Even the first word of
output gives a non-negligable amount of information about the file
(since there are less than 2^32 irreducible 32-bit polys, some
input files are impossible for a given output).
[Can I have a general whinge that people should not try to design
AONTs unless they understand what an AONT is, and in particular how
strict the definition of that term is? There have been several
instances of this recently on sci.crypt.]
[1] Victor Boyko,
"On All-or-Nothing Transforms and Password-Authenticated Key
Exchange Protocols,"
PhD Thesis, MIT, June 2000.
(should be somewhere at http://www.toc.lcs.mit.edu/~boyko/, but
that seems to be down at the moment)
[2] Yevgeniy Dodis,
"Exposure-Resilient Cryptography,"
PhD Thesis, MIT, August 2000.
http://www.toc.lcs.mit.edu/~yevgen/ps/phd-thesis.ps
- --
David Hopwood <[EMAIL PROTECTED]>
Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOkpUWDkCAxeYt5gVAQG7AAgAkhIfOVunss90C/cLQSoT80y8c6AVigl/
eMc/PsY20QpsZvl/oNvOqwkuxROFWzrjDRsFueKOkLXHGVJ3nekgqQivEMWq/SkF
nW7PJu0Ix0HCTqwdAONkzD0Uo3GhZMlDyMA37ADRQaJkcNZaanSy88evmjob0T5a
smriwa39MHLuy7nSP1ne5rvUpB+Be8W9Y+pdDh9XSKQXCRTq43H5cNdsgtydofNQ
Va6lclBpAkimSFVdbCzB9SeYUFx6v+rDEKqEz4k1y60+81RhA5Foj3zCsYFUpZUA
VkSULmf1gjt2p2Rn+i+Xq0Dic3D1W68e4vOVa6I3RG3EDYnfE+Tgpg==
=8972
=====END PGP SIGNATURE=====
------------------------------
Date: Wed, 27 Dec 2000 07:24:58 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Foolproof Quantum Cryptography
=====BEGIN PGP SIGNED MESSAGE=====
Dido Sevilla wrote:
> IIRC, the ion trap
> team was only able to produce two qubits, while the bulk spin resonance=
> team four, meaning that the largest number that they can try factoring
> using Shor's algorithm is only 15!
Shor's algorithm requires *at least* four times as many qubits as the num=
ber
of bits in the number, plus some working space, plus qubits used for erro=
r
correction.
Source: sections 3.4 and 3.5 of
Arthur O. Pittenger,
"An Introduction to Quantum Computing Algorithms,"
Berkh=E4user, 1999.
ISBN 0-8176-4127-0
(note in section 3.5 that n ~ lg(N^2), and two n-qubit registers are
used, which is at least 4lg(N) qubits excluding error correction).
So "the largest number that they can try factoring using Shor's algorithm=
is only 1!" However, I do believe another team has since reached 7 qubits=
,
which means it might soon be possible to factor the number 2 (except that=
Shor's algorithm only works for odd moduli, darn it :-)
- -- =
David Hopwood <[EMAIL PROTECTED]>
Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 0=
1
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has b=
een
seized under the Regulation of Investigatory Powers Act; see www.fipr.org=
/rip
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOkmZCjkCAxeYt5gVAQG/RAf9GW0+zheohevTWgNWPvxoMRlzz4YN/GPi
cstEh+6qKz/9dqFgFKG+v5Xwa+O9HKMINPlon9YK5OSkQ+z6tZBH6SizlDpBxfxx
KbjZ62zCAZiuNrj8MVgvbQVfJn/CmZulYygT/io5AyuBo87DRMUhNsYsluJytfWt
rhod9BlPmH1b1lgs2cUb1LnJzoftTmalSG/RT44Xhj6jXjBYE63YBZ+t6sBuFgf2
KxYstjyuq61Ykz5E5PLmU+uzIPVqMoUfYT1FH57bwKUgNToepxKvQxEPusv2Ej4n
odKad4kPTSEHA2+LxUpJoukH8PWKyT3c2W9ZjGc0TprcrNPxKRp7tg=3D=3D
=3DfxES
=====END PGP SIGNATURE=====
------------------------------
Date: Wed, 27 Dec 2000 07:35:01 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Foolproof Quantum Cryptography
=====BEGIN PGP SIGNED MESSAGE=====
Steve Portly wrote:
> Simon Jenkins wrote:
> > Just to sidetrack a bit on quantum cryptography (of which I am no
> > expert), it seems to me that, if I wanted to stop anybody using it, I
> > would just intercept all their messages. They would be aware the messages
> > had been intercepted because (I think) the photon states would have
> > changed and the message they received with therefore be garbage, forcing
> > them to use a more accessible system.
> >
> > Or maybe I'm wrong.
>
> A denial of service attack would be practical in most cases however one of
> the articles mentioned the primary use would be for rekeying satellites.
... which is a silly idea, because if you are using quantum crypto just
for rekeying conventional (symmetric or public key) algorithms, you might
as well use conventional methods for the rekeying step as well. It
will be no less secure, and may well be more secure because you are
relying only on cryptographic assumptions, rather than cryptographic
assumptions *and* physical assumptions about the lack of side channels
or other flaws in the quantum transmitters/receivers.
- --
David Hopwood <[EMAIL PROTECTED]>
Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOkmbmjkCAxeYt5gVAQHYuQgAkLi4YZYf4J/dnYicY+ovJmiSB4vWzVNO
jgoOcAoaX/LePy1xtVgSeixgS6ECZxbk/0CjP+PPYQZ0AcCKubixVHRUCjbTjoOf
uZUyZFqr3oE+cZ+i6dYyUp3X2XmEeFB4v7IkJiFvnSkY9Ib/j2TJBGKjrXv00BF5
S2LNIOkuQPhF1azNQZyjoB499rJ9wn5l4NLKShaMv6zNFILO9GxhxA1Asm2w5CTV
7OywBTsWunaJjuhSQi4PZ3/yXgv2q9fwCPf5LIkiu1q8OYA37Gm0JNJGpVOObYmt
F43tTFE73wsFnKfDVULAYSOAU3C1kIA7Ipj3lJW/bGwT/QYNnfijrw==
=aoQt
=====END PGP SIGNATURE=====
------------------------------
Date: Wed, 27 Dec 2000 07:47:20 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: RSA == hash function?
=====BEGIN PGP SIGNED MESSAGE=====
[EMAIL PROTECTED] wrote:
> I think RSA cannot be considered as a hash function because its input
> and output length is a variable depending on the modulo n. Hash
> function should take variable input length and produce fixed length
> output.
That is not why RSA is not a hash function. It would be perfectly
possible to fix the length of n, and in any case other hash functions
have variable output lengths depending on a parameter.
RSA is not a (secure) hash function because it is invertible when the
factors of the modulus or the decryption exponent d are known (and if
someone gives you a modulus claiming that the factors and d have been
discarded, there is no way for you to verify that).
Also, the RSA primitive is a multiplicative homomorphism
(RSA_pk(x) * RSA_pk(y) = RSA_pk(x*y)), which is not a property that a
hash function should have.
- --
David Hopwood <[EMAIL PROTECTED]>
Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOkmeNDkCAxeYt5gVAQGvuAgAxqjXMQUoR1E4svoj+IGFE02u/ICVQl2D
r+uGXR0ZZZYcerL7jW/eIsOJxmDOD6wcmYFwDpEFboQv+iGOjSutnwboGlhcnJxL
5oSXZ2YYuFzmlNrDxRg6sn357KVyM0FXaKRiGPLmvAZoa5o1uVbbs0tQBDHV+kS3
gF/Igqg4/BTcWXdP9dHkbHIjtz5erm6Fq1kyxpoTlq0JZai7CpcHtUmFaNW3quH2
1PLYto0aGSuymy3HxkhECUQa4tSHMBFO/itwpmLfdshXQVxpSWtR7r8QebPKCmLA
a3iECR0J8UXByxUSqXqt4L7uVvHni3Xy7BWV6d62LePgb2Iay7oQzA==
=wwNr
=====END PGP SIGNATURE=====
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: MD5 and hash127 questions
Date: Wed, 27 Dec 2000 13:04:47 -0800
> Hi, I have two questions: 1 Mr.Bruce Schneier's "Secrets and Lies" book,
page
> 94, 5 lines from the bottom: " ...MD5 is showing some cracks and is not
used
> for anythong new." Is this true? What kind of cracks?
That should read "should not be used" instead of "is not used" As others
have said a collision has been found in the compression function. While for
high security purposes this is a critical problem, there are purposes where
this crack is of little interest. It is as always a consideration of what
your actual threat/security model is.
> What about TCP/IP syn
> cookies - they are almost new and they use MD5.
If TCP/IP syn cookies were ever considered a high-security purpose, I think
it would be folly, the use of MD5 simply makes it more apparent to the
layman.
>
> 2. Some oppinions about Mr. D.JBernstein's hash127 and sigs packages. Can
I
> make ASCII armored ciphertext with them?
You can make armored ciphertext with just about anything, but that is due to
the fact that armoring ciphertext typically refers to base-64 encoding it to
pass through text-based systems. As to the security of them, like the others
I haven't examined them, however Bernstein is not an unknown to our
community, if it truly is by his authoring then there is likely something to
it, if it isn't than the impersonation alone would be more than enough to
eliminate them permanently from the use of the reasonable.
Joe
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: GIF image 1x1 pixels (sic)
Date: Wed, 27 Dec 2000 15:08:18 -0600
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (wtshaw) wrote:
> In article <92be4j$8lv$[EMAIL PROTECTED]>, Simon Johnson
> <[EMAIL PROTECTED]> wrote:
> > >
> > What could you encrypt into a 1 pixel? There just isn't enough data to
> > give the pixel context.
> >
> Ask yourself what 8 to 32 bits can be used for, an amount if information
> that a pixel usually does contain in formats with pixel fidelity.
Concerning a "transparent" webbug, which is another question, to some
browsers, they aren't transparent at all.
--
I heard that Bill Clinton may further his career as an actor with
the lead role in the story of Benny Hill's life.
------------------------------
From: [EMAIL PROTECTED] (MCKAY john)
Subject: Re: Q: Result of an old thread?
Date: 27 Dec 2000 21:55:37 GMT
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
>
>Walter Hofmann wrote:
>>
>> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>> >
>> >Let me quote a previous follow-up of yours to be sure that
>> >I understand you:
>> >
>> > So you can change the coefficiants of AS by a sufficiently
>> > small epsilon>0 to get an invertible matrix, then you can
^^^^^
There is no "small" over these finite fields. You need a decent metric.
JM
>> > calculate (AS')^-1. Go on to calculate B'=(AS')^-1.ASB
>> > then S(epsilon)=SB.B'^-1. In the limit epsilon->0 the
>> > matrix S(epsilon) will converge to S as all operations
>> > involved are continuous.
>> >
>> >You defined B'=(AS')^-1.ASB. But ASB is singular, so B'
>> >can't be inverted. Or do you want to apply the epsilon to
>> >ASB also?
>>
>> Now I see what you mean: You cannot invert B' here because I put
>> another factor of S in it.
>>
>> It's probably the best to compute things the other way round, otherwise
>> one would need two epsilons:
>>
>> Change ASB to ASB' which is within an epsilon of ASB.
>>
>> Then you can calculate
>>
>> B'^-1 = ASB'^-1 . AS
>> S = SB . B'^-1
>>
>> and do the limit process as described above.
>>
>> Is this OK with you now?
>
>I still think that your limit process is problematic,
>for on a computer with fixed word size there is a certain
>delta such that anything smaller than that will be
>treated as zero (underflow), so the limiting process
>can't be carried out in all situations. On the other
>hand the argument of Jacob Jonnson that there is a good
>probability of obtaining a non-singular matrix to solve
>the problem does seem to be useful in general cases.
>
>M. K. Shen
--
But leave the wise to wrangle, and with me
the quarrel of the universe let be;
and, in some corner of the hubbub couched,
make game of that which makes as much of thee.
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: polynomial permutation cipher
Date: Wed, 27 Dec 2000 22:27:12 GMT
Benjamin Goldberg wrote:
> Now consider t[0] % py[0]. Since
> t[0] is a multiple of ct[0], t[0] % py[0] == ct[0] % py[0].
I think Shen is basically right; there's a mistake in that
last inference. Since t[0] is a multiple of ct[0], we can say
t[0] = z * ct[0]
so
t[0] % py[0] == (ct[0] % py[0]) * (z % py[0]) % py[0]
Your conclusion is true only if z is congruent to 1 modulo
py[0]. Since z is the product of the other polys, that
probably will not be true. You could multiply each t[i] by
the mod py[i] inverse of the product of the other polys. That
does get you into taking inverses as Shen suggested, but will
only add Theta(n^2) to the run time which is already
Theta(n^3).
You also need to modulate by the product of all the polys.
The proposed flipping of the x^128 bit is not correct.
Garner's algorithm does CRT reconstruction in Theta(n^2) time,
including computation of the inverses. It's in HAC as
algorithm 14.71, currently on-line for free at:
http://www.cacr.math.uwaterloo.ca/hac/
Below I've included a large integer version in Python.
--Bryan
Garner's CRT reconstruction algorithm in Python:
|
| def inverse_gcd(x, n):
| """Return (a, d) such that for some integer y:
| a*x - y*n == d == gcd(x, n).
| """
| y, a, b = n, 1, 0
| while y>0:
| x, (q, y) = y, divmod(x, y)
| a, b = b, a - b*q
| if a < 0:
| a = a + n
| return a, x
|
| def inverse(u, v):
| """Returns the mod v inverse of u."""
| (result, gcd) = inverse_gcd(u, v)
| if gcd != 1:
| result = None
| return result
|
| def garner_inverses(factor_list):
| """Return the list of inverses used by Garner's algorithm.
| Pass a list of n relatively prime factors. Returns a list
| of n inverses, where inverse[i] is the mod factor[i] inverse
| of the product of the preceding factors. The product of
| zero factors is 1.
| """
| inverse_list = []
| prod = 1L
| for p in factor_list:
| inv = inverse(prod, p)
| assert inv, "Factors were not all relatively prime."
| inverse_list.append(inv)
| prod = prod * p
| return inverse_list
|
|
| def garner(residues, factors, inverses=None):
| """Given lists of residues and relatively prime factors, return
| the one integer in [0..product of factors) that is congruent to
| residue[i] mod factor[i] for each i.
| Optionally pass the inverses for the factors, as returned by
| garner_inverses. Returns zero given empty lists.
| """
| count = len(residues)
| assert len(factors) == count
| if not inverses:
| inverses = garner_inverses(factors)
| assert len(inverses) == count
| (x, r) = (0L, 1L)
| for i in range(count):
| u = (residues[i] - x) * inverses[i] % factors[i]
| x = x + u * r
| r = r * factors[i]
| return x
|
|
| # Brief demo:
|
| def crt_reduce(m, primes):
| l = []
| for p in primes:
| l.append(m % p)
| return l
|
| moduli = [31, 101, 71, 1000003, 1007, 100001]
|
| m = 9384719571710914514L
|
| res = crt_reduce(m, moduli)
|
| mz = garner(res, moduli)
|
| print m
| print mz
|
| # Prints:
| # 9384719571710914514
| # 9384719571710914514
|
Sent via Deja.com
http://www.deja.com/
------------------------------
From: [EMAIL PROTECTED] (Tim Olson)
Subject: [rijndael] Efficient hardware S-box implementation
Date: Wed, 27 Dec 2000 17:06:42 -0600
On the Rijndael homepage, there is a paper titled "Efficient
Implementation of the Rijndael S-Box". The paper states that the
difficult part of the S-box implementation is finding the multiplicative
inverse of an element in GF(256). In general, this would be a lookup into
a 256-entry, 8-bit table.
It goes on to state that this may be simplified by representing elements
in GF(256) as a 1st-degree polynomial with coefficients in GF(16):
(bx + c)
with addition defined as vector addition with GF(16) coefficients, and
multiplication as vector multiplication modulo some irreducible degree-2
polynomial x^2 + Ax + B.
However, I cannot find an easy mapping from the representation of elements
in GF(256) to the 2 coefficients b & c in GF(16) -- it appears to be just
as hard as the "brute-force" table lookup method for finding the
multiplicative inverse in GF(256).
Does anyone have an idea of how this might work?
--
-- Tim Olson
------------------------------
** 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
******************************
