Cryptography-Digest Digest #224, Volume #12 Fri, 14 Jul 00 05:13:01 EDT
Contents:
Re: cray and time needed to attack (Jerry Coffin)
Re: Concepts of STRONG encryption using variable base http://www.edepot.com/phl.html
(Jerry Coffin)
Re: On intermixing as encryption processing (David Hopwood)
Re: Diffie Hellman Primes : Speed Tradeoff Q (David Hopwood)
Idea for CFB-like cipher (Benjamin Goldberg)
Re: Is there any bright mind who have 5 seconds to spare? (Benjamin Goldberg)
Re: Computing with Encrypted Functions (Paul Rubin)
source code CD -from Burce Schneier (applied cyotopgraphy) ([EMAIL PROTECTED])
Re: Proposal of some processor instructions for cryptographical applications
("Stefan Monnier " <[EMAIL PROTECTED]>)
Re: On intermixing as encryption processing (Mok-Kong Shen)
Re: Diffie Hellman Primes : Speed Tradeoff Q (Mark Wooding)
Re: Has RSADSI Lost their mind? (Mark Wooding)
Re: source code CD -from Burce Schneier (applied cyotopgraphy) ("Hans Husman")
Re: Diffie Hellman Primes : Speed Tradeoff Q (Mark Wooding)
Re: Random Numbers (David Bernier)
Re: Q: Hadamard transform (Simon F)
----------------------------------------------------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Subject: Re: cray and time needed to attack
Date: Fri, 14 Jul 2000 00:23:11 -0600
In article <8km7rs$mtr$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
says...
[ ... ]
> No, that was not addressing my question, but you did give me the
> answer - the key will deliver the entire message, correct?
At least IIRC, the original question was about Diffie-Hellman. If
so, technically speaking no, breaking it will not give you any
particular message by itself. Diffie-Hellman is a method of
exchanging a key in a secure manner. Breaking it will (normally) get
you a key that you can then use to decrypt the rest of the real
message. OTOH, once you have the key this second part is normally so
trivial it's hardly worth talking about -- at this point, you
basically have the same amount of work to read the message (yes, the
whole message) as the intended recipient would have.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Subject: Re: Concepts of STRONG encryption using variable base
http://www.edepot.com/phl.html
Date: Fri, 14 Jul 2000 00:23:13 -0600
In article <8km75f$ma2$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
says...
[ ... ]
> How much time would a 256 bit Twofish key space require?
Long enough that unless you find a break against TwoFish, it's not
even worth contemplating. We're talking in terms of multiples of the
currently-estimated age of the universe here.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
Date: Thu, 13 Jul 2000 21:15:48 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: On intermixing as encryption processing
=====BEGIN PGP SIGNED MESSAGE=====
Mok-Kong Shen wrote:
> Let two ciphertext bit sequences c1_i and c2_i be given,
> e.g. being outputs from some block ciphers. With a
> real-valued uniformly distributed pseudo-random variable
> r() in [0,1), we can do multiplexing to produce one combined
> bit stream u_i as follows:
>
> i=j=k=0;
> do
> i=i+1;
> if r() < 0.5 then j=j+1; u_i = c1_j
> else k=k+1; u_i = c2_k fi;
> od
>
> That is, we intermix the bits of the two given streams in
> such a manner that the resulting bits have equal chance of
> being originated from the one stream or the other.
>
> Obviously this materially enhances the difficulty of the
> opponent,
I don't see that this is obvious at all; it depends how the input
bit streams can be attacked. If either of the two mixed streams are
biased, for example, then the output will also be biased. As a method
of combining three (including r()) possibly-random bitstreams in order
to produce a hopefully stronger bitstream, I don't see that this method
is very efficient or effective.
> since he has to identify (guess) which bits of
> u_i belong to the first stream and which to the second.
That may or may not be true.
- --
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
iQEVAwUBOW4jZDkCAxeYt5gVAQG+RAf+Kjk4KIBgqFdFXkgp1FxOak6d2WtDBvNy
M73en/ZUH5A0KLCNWsfgPea46zISGciK4yKchkiSfZ2oU6Pe3oULi5ZZ4VqY0Bxs
l5Pw9LfZQPQnVElhN7KtbgPOVysoNzvLql7lP1JP4u+kW2tAzh8THPVqkUQtCeMn
9Jj3OjLVQFX2F8MidgTXJaDUtZtgD4wGOeACaqGf/b2TY5UR+1hNIPV1VZYYW+2C
kILGtqCAms/l86A3+QB1jmRhUW94P0dWAJFhbGThg62aDsYmi6wrSPnU9LjdzyFF
Ryja5aWLN/EDyML8xqEHfbVX3fTlJyAoAvWG5p9p9DpsBs1R+ZgjKA==
=IV5L
=====END PGP SIGNATURE=====
------------------------------
Date: Thu, 13 Jul 2000 21:45:34 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Diffie Hellman Primes : Speed Tradeoff Q
=====BEGIN PGP SIGNED MESSAGE=====
<sigh>. I should spend more time proof-reading.
David Hopwood wrote:
> David Hopwood wrote:
> > Mark Wooding wrote:
> > > Anton Stiglic <[EMAIL PROTECTED]> wrote:
> > > > Lim-Lee primes, primes of the form p = 2*q_1*q_2*...*q_n + 1, where
> > > > the q_i's are large work fine. You can simply work in one of the
> > > > subgroups of large prime order.
> > >
> > > That only partially answers my question. Do we have a problem if we do
> > > arithmetic mod p = q R + 1, where q is a large-ish prime, p is large,
> > > and R is a random composite (therefore possibly having small factors,
> > > but also likely to have fairly large ones), and work in the subgroup of
> > > order q?
> >
> > Yes. See van Oorschot and Wiener's paper:
[...]
> Sorry, I got that wrong. The van Oorschot-Wiener attack only applies to
> short exponents in the full group, not when a Lim-Lee prime is used,
> even when R has small factors. (The reason why it doesn't work is that
> the partial Pohlig-Hellman decomposition can't be computed when g is
> of prime order.)
>
> Nevertheless, I would still recommend p = qR + 1 with R prime as the
> simplest and most efficient way in practice to avoid all of the attacks
> on short exponents.
This should be p = 2qR + 1 with R prime.
> It certainly doesn't do any harm to have R prime,
> and it means that there are no elements of order less than q in the
> range [2, p-2]. I.e. you can check that an element has large order very
> efficiently in this case (which is important because otherwise, checks
> on the order of the transmitted elements may take as much time as is
> saved by using the subgroup).
This is still right - the possible orders of an element are
1, 2, q, 2q, R, 2R, qR, and 2qR. The element 1 has order 1, p-1 has
order 2, and all the rest (i.e. in [2, p-2]) have order >= q.
> Incidentally, if p is going to be common between users, it's best to
> generate it using something like:
>
> R := next_prime(first n bits of pi)
> q := next_prime(next m bits of pi)
> while (qR + 1 is not prime)
^^ should be 2qR
> q := next_prime(q+1)
>
> where next_prime(k) is the lowest prime >= k.
- --
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
iQEVAwUBOW4qKDkCAxeYt5gVAQHjpggAiCb3o2TpvTJR76mVX/lq0yppR567ggyH
+4NJvMNVgjhnSgiwNabpeqgGF0H7Dj14ayZpA9qyjQdh7y6fUMxZrSz3e29msu8H
JT6WAJNL3euamONZrXIaUzJ3Sj/27yOTGvrEDOdCEtr1DqpOTJovRLewCOLFelSZ
onh7ffRHnvtDhN7NJqHNHXFDQQBGBfc2x5UpBnJjcDg7zQ6Th6Y1dJioJj2cNeyZ
scau+wHwGgbmmZ3b0Gcp+kJHaiBHA9kHc3rJcm4MXbmX5GxKWNiDOtWeLay5h1Kr
jtyOknclkXAGbyUvCOcB8UW5UwMbMOuLlqotGk43t9T2i5f1in+acQ==
=o5TG
=====END PGP SIGNATURE=====
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Idea for CFB-like cipher
Date: Fri, 14 Jul 2000 06:52:01 GMT
After reading the description of the 'Cipher FeedBack' mode of chaining
for DES, where the last 64 bits of ciphertext were encrypted, and one
bit of this was XORed with one bit of plaintext to get the next
ciphertext bit, I came up with the following idea: Using a small, fast,
secure keyed hash, do something similar. CFB in DES is slow and
inefficient, but that's because DES is designed for 64 bit output; we
can easily make a hash that is designed to have an 8 bit output.
This has probably been done before, but who knows?
IV = initialization vector.
PT[0..] = plaintext
CT[0..] = ciphertext
H_K = a keyed psuedorandom function {0,1}^(8N) -> {0,1}^8
Algorithm:
CT[-N .. -1] = IV
CT[i] = PT[i] XOR H_K( CT[i-1 .. CT[i-N] )
The H I would use is more-or-less grabbed from lja1:
/* K is the key, in is the input, N in the size */
/* K is a shuffled array 0..255, which has been */
/* changed so that for all i, K[i] != i */
char H(char *K, char *in, int N) {
int i, out;
for( i = out = 0; i < N; ++i )
out = key[out+key[in[i]]];
return (char)out;
}
--
This is the signature worm.
Help me spread by appending me to your signature.
This is the signature worm.
Help me spread by appending me to your signature.
This is the signature worm.
Help me spread by appending me to your signature.
This is the signature worm.
Help me spread by appending me to your signature.
This is the signature worm.
Help me spread by appending me to your signature.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Is there any bright mind who have 5 seconds to spare?
Date: Fri, 14 Jul 2000 06:52:04 GMT
Ichinin wrote:
>
> Hi people.
>
> I'm trying to create a feistel cipher for fun.
> Still, it's not reversible (Ok, it 75% "reversible" :oP)
>
> So what's the smeg is wrong with it?
> ______________________________________
>
> Partial source:
>
> - The F() function IS 100% reversible (Belive me, i've checked.)
> - I'm starting at X-1 as i should do [0]
Bzz! Sometimes you're starting at X, sometimes you're
starting at X-1. You've got some confused code.
If instead of having X=1..16, and index with X-1,
you had X=0..15, and indexed with X, you would have
lots fewer problems.
--
This is the signature worm.
Help me spread by appending me to your signature.
This is the signature worm.
Help me spread by appending me to your signature.
This is the signature worm.
Help me spread by appending me to your signature.
This is the signature worm.
Help me spread by appending me to your signature.
This is the signature worm.
Help me spread by appending me to your signature.
This is the signature worm.
Help me spread by appending me to your signature.
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: Computing with Encrypted Functions
Date: 14 Jul 2000 06:52:56 GMT
In article <8kjci8$j9h$[EMAIL PROTECTED]>, Austin Godber <[EMAIL PROTECTED]> wrote:
>"The idea is to encrypt a function f to obtain some other function E(f)
>that hides the function f. This encrypted function can then be
>implemented as a program P(E(f)), which is interpreted as a mobile
>agent and sent to the agent executor. The latter can execute the mobile
>agent P(E(f)) on an input value x, which leads to the encrypted result:
>P(E(f))(x). Since the agent executor does not know what function it
>actually computed, it can not meaningfully tamper with the code or its
>execution and is restricted to random modifications (which result in
>denial-of-service) and replay attacks. The encrypted result is returned
>to the agent owner who can apply the decryption function, that only he
>knows, to obtain the desired result of the function f applied to the
>input value x: E^1(P(E(f))(x)) = f(x)."
Well, if they have a workable method in general for doing that, among
other things it makes identity-based encryption trivial.
------------------------------
From: [EMAIL PROTECTED]
Subject: source code CD -from Burce Schneier (applied cyotopgraphy)
Date: Fri, 14 Jul 2000 06:51:06 GMT
Does nay one used source code CD -from Burce Schneier (applied
cyotopgraphy)
3DES code does not work, does not have any test code or main() function
I am pretty new to crypto..., And I am stck on a project.
Thanks
Stellus
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Stefan Monnier <[EMAIL PROTECTED]>" <[EMAIL PROTECTED]>
Crossposted-To: comp.arch
Subject: Re: Proposal of some processor instructions for cryptographical
applications
Date: 14 Jul 2000 03:23:43 -0500
>>>>> "Douglas" == Douglas A Gwyn <[EMAIL PROTECTED]> writes:
> "Stefan Monnier " wrote:
>> I'm sure you know that doing such things when the cast changes an
>> (int*) into a (char**) is rather difficult.
> Perhaps you should give an example, since such a cast on most
> common architectures doesn't require any code generation at all.
You said that when casting int to char*, a bit-addressed architecture
could provide the illusion of sizeof(char)==1 by shifting the int
value by 3 bits (assuming chars are 8bit).
But then c1 and c2 in the following code won't be the same anymore
unless you do something very funky with casts from int* to char**:
void f (int n)
{
char *c1 = (char*)n;
char *c2 = *(char**)&n;
....
}
-- Stefan
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: On intermixing as encryption processing
Date: Fri, 14 Jul 2000 10:35:02 +0200
David Hopwood wrote:
> Mok-Kong Shen wrote:
> > Let two ciphertext bit sequences c1_i and c2_i be given,
> > e.g. being outputs from some block ciphers. With a
> > real-valued uniformly distributed pseudo-random variable
> > r() in [0,1), we can do multiplexing to produce one combined
> > bit stream u_i as follows:
> >
> > i=j=k=0;
> > do
> > i=i+1;
> > if r() < 0.5 then j=j+1; u_i = c1_j
> > else k=k+1; u_i = c2_k fi;
> > od
> >
> > That is, we intermix the bits of the two given streams in
> > such a manner that the resulting bits have equal chance of
> > being originated from the one stream or the other.
> >
> > Obviously this materially enhances the difficulty of the
> > opponent,
>
> I don't see that this is obvious at all; it depends how the input
> bit streams can be attacked. If either of the two mixed streams are
> biased, for example, then the output will also be biased. As a method
> of combining three (including r()) possibly-random bitstreams in order
> to produce a hopefully stronger bitstream, I don't see that this method
> is very efficient or effective.
>
> > since he has to identify (guess) which bits of
> > u_i belong to the first stream and which to the second.
>
> That may or may not be true.
>
The processing here introduced is not stand-alone but is a step
supplementary to an encryption algorithm and enhances its strength.
That maxing something together (in other context) renders the
separating the stuffs out rather difficult is a common experience
and should be intuitively clear.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Diffie Hellman Primes : Speed Tradeoff Q
Date: 14 Jul 2000 08:40:51 GMT
Bob Silverman <[EMAIL PROTECTED]> wrote:
> Huh? They still take O(sqrt(q))! As long as q is large, the structure
> of R doesn't matter.
Does the structure of p, containing as it does many small factors, not
make attacks against the cyclic group of the whole field easier?
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Has RSADSI Lost their mind?
Date: 14 Jul 2000 08:44:14 GMT
Paul Rubin <[EMAIL PROTECTED]> wrote:
[Diffie-Hellman in SSL]
> The trouble is that not that many browsers support it.
Indeed. Is there any good reason for this? It would save me worrying
about keys being demanded from the server admins and decrypting past
sessions.
I have a policy for protocols I design now: all long-term secrets are
signing keys, because they tend to be given special exceptions from GAK.
-- [mdw]
------------------------------
From: "Hans Husman" <[EMAIL PROTECTED]>
Subject: Re: source code CD -from Burce Schneier (applied cyotopgraphy)
Date: Fri, 14 Jul 2000 10:49:25 +0200
Well you could try some of the implementations at
ftp://ftp.funet.fi/pub/crypt/cryptography/symmetric/des/
instead.
Best Regards
============================================================================
=========
Hans Husman
Security Specialist
Mynta Management & IT AB
[EMAIL PROTECTED]
+46 (0)70 370 22 17
http://www.mynta.se
============================================================================
=========
Prenumerera p� n�got av Myntas nyhetsbrev!
Mynt@. Ett nyhetsbrev fr�n en elektronisk aff�rsv�rld.
S�ker med Mynta. En elektronisk tidning om datas�kerhet.
Skicka ett mail till [EMAIL PROTECTED] och ange vilket nyhetsbrev du vill ha.
============================================================================
=========
<[EMAIL PROTECTED]> wrote in message news:8kmd8n$qb1$[EMAIL PROTECTED]...
> Does nay one used source code CD -from Burce Schneier (applied
> cyotopgraphy)
> 3DES code does not work, does not have any test code or main() function
> I am pretty new to crypto..., And I am stck on a project.
> Thanks
> Stellus
>
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Diffie Hellman Primes : Speed Tradeoff Q
Date: 14 Jul 2000 08:55:27 GMT
Bob Silverman <[EMAIL PROTECTED]> wrote:
> Huh? They still take O(sqrt(q))! As long as q is large, the structure
> of R doesn't matter.
If you do Pollard's rho in the subgroup, yes. When I wrote my comment,
I expected that the structure of p = q R + 1 (R smooth) would help in
attacks against the entire multiplicative group of GF(p) (with discrete
logs in the q-order subgroup as a consequence).
I no longer believe this, having consulted the HAC again, but I'm open
to further enlightenment on this issue.
-- [mdw]
------------------------------
From: David Bernier <[EMAIL PROTECTED]>
Subject: Re: Random Numbers
Date: Fri, 14 Jul 2000 08:50:12 GMT
In article <8kfs9g$bdk$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Bill Unruh) wrote:
> In <8kfbpm$[EMAIL PROTECTED]> [EMAIL PROTECTED] (Guy
Macon) writes:
> ]>>Sorry I left out some detail about the random bit stream. The bit
stream
> ]>>has been generated from a white noise source I built from a zener
diode, a
> ]>>couple of op-amp stages and a comparator. Although the bits
produced are
> ]>>independent of each other, there is a bias that can't be removed by
> ]>>adjusting the dc mean level of the noise. Therefore I was asking
if there
> ]>>is a way of processing the bit stream to produce 16-bit random
numbers with
> ]>>a uniform distribution?
>
> Unfortunately you do not know that the bits are independent. Physical
> processes often have long range correlations (eg stray capacitances
etc
> can produce oscillations in the circuit which introduce correlations
in
> the output of the zenner.) You really need a good physical model for
> the system, and then look for correlations produced by that model.
I've heard of Marsaglia's "die-hard" tests. There's a test I've
thought of and I don't know whether it's been studied/used before.
It involves studying the Bernoulli-likeness of blocks of L
consecutive pseudo-random bits. Suppose L= 65536. Then we can
divide the bitstream into blocks of 65536 consecutive bits and, for
one block, take the arithmetic sum of all 65536 bits. Suppose
the blocks are L_1, L_2, ... L_N, and the sums s_1, s_2, ...
s_N . So 0<=s_k <=65536. In an array A of length 65537 indexed by i,
we would let A[i] be the number of times that the sum s_k is i for
0<=i<= 65536. So the sum of the A[i]'s is N. The expected value
of A[i] is: (1/2)^N * C(65536, i) * N, 0<=i<=65536. Then a
chi^2 like goodness of fit test could be done on a sub-sequence
of the A[i] (say for |i-32768|< 500, depending on how large N is).
Since the memory requirements are modest, even with L=65536,
it seems feasible to use L=2^20, say, e.g. using dynamic memory
allocation/linked lists in C or another programming language.
David Bernier
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Simon F <[EMAIL PROTECTED]>
Subject: Re: Q: Hadamard transform
Date: Fri, 14 Jul 2000 08:53:46 GMT
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
>
> > > There exists 2-D Fourier transform. Does anyone have literature
> > > pointer of an analogous 2-D Hadamard transform? Thanks in advance.
> >
> > In a texture compressor (for Dreamcast) I used Hadamard transforms
to
> > extract frequency information.
> >
> > Assuming that you have an n*n matrix of values, M, (where n is a
power
> > of 2), I just used:
> >
> > Result = 1/n^2 * (Hn * M * "Hn-transpose")
> >
[SNIP]
>
> Suppose you stretch out your two dimensional data to become a one
> dimensional sequence, would you get poorer or better informations
> for your purpose? And why? Thanks.
AFAICS the result would be worse because flattening it into 1 dimension
would favour, say, Y over X. Since I'm analysing an image, X & Y should
be handled equally. Of course, processing encrypted data may be a
completely different matter.
Simon
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
** 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
******************************
