Cryptography-Digest Digest #741, Volume #13 Fri, 23 Feb 01 22:13:01 EST
Contents:
Simple, possibly flawed, stream cipher (Benjamin Goldberg)
Re: á÷ôïûéîù éú ñðïîéé, îå äïòïçï!!!!!!! ("Glenallan")
Encrypted Email for Business Documents (Peter Harrison)
Re: Freq analysis of a possible cyphertext. ("Stefan Habenschuss")
Re: MIKE alternative to SPEKE and PAK (long) ("Michael Scott")
Re: Super strong crypto (Benjamin Goldberg)
[OT] Re: Really big numbers in C ("Trevor L. Jackson, III")
Re: Simple, possibly flawed, stream cipher (David Wagner)
Re: question1,2,2a,3,4,5,5a,5b,5c,6 (Kat Hopwood)
Re: Processing on cyphertext (Kat Hopwood)
Re: Simple, possibly flawed, stream cipher (David Wagner)
Re: Really big numbers in C (Bob Day)
Re: Really big numbers in C ("Joseph Ashwood")
Re: Simple, possibly flawed, stream cipher ("Henrick Hellström")
Re: super-stong crypto, straw man phase 2 ("Henrick Hellström")
Re: __(?) MATRIX version of Fermat's Little Theorem ("Brian McKeever")
----------------------------------------------------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Simple, possibly flawed, stream cipher
Date: Sat, 24 Feb 2001 00:27:58 GMT
I've thought about this idea for the last couple of days, and I haven't
yet figured out what kind of weakness(es) it has.
uint8 state[8] = { key };
uint8 sbox[256];
for( i = 0, x = 1; i < 8; ++i )
x ^= sbox[ state[i] += (x>>i) & 1 ];
keystreambit := x;
I can't help but think that there's got to be a flaw here somewhere,
since it's so simple, but I can't see where.
Also, I'm not quite certain what properties sbox should have --
especially if I want the cipher to have the maximum period.
One nice thing I can see about this, though: By unrolling and
pipelineing, it should take one clock cycle per byte of output.
--
A solution in hand is worth two in the book.
------------------------------
From: "Glenallan" <[EMAIL PROTECTED]>
Crossposted-To:
relcom.www.users,relcom.x,sci,soc,soc.culture,soc.culture.brazil,soc.culture.irish,soc.culture.israel,soc.culture.scottish
Subject: Re: á÷ôïûéîù éú ñðïîéé, îå äïòïçï!!!!!!!
Date: Sat, 24 Feb 2001 00:41:09 -0000
OK Nikk,
I surrender. What is this one about.?
If this is 'Doric', I am emigrating to England.
Glenallan
=========
"kononec" <[EMAIL PROTECTED]> wrote in message
news:9767sh$2rnc$[EMAIL PROTECTED]...
> þð "ëÏÎÏÎÅÃ" ÐÒÅÄÌÁÇÁÅÔ ËÏÎÔÒÁËÔÎÙÅ ÐÏÓÔÁ×ËÉ ËÒÕÐÎÙÍ É ÍÅÌËÉÍ ÏÐÔÏÍ
Á×ÔÏÛÉÎ
> ÉÚ ñÐÏÎÉÉ.
> ÷ ÎÁÌÉÞÉÉ ÉÍÅÀÔÓÑ Á×ÔÏÛÉÎÙ ×ÓÅÈ ÒÁÚÍÅÒÏ×, Á ÔÁËÖÅ ÌÉÔØ£ ÒÁÚÎÙÏÏÂÒÁÚÎÙÈ
> ×ÉÄÏ×. ôÏ×ÁÒ ×Ù ÍÏÖÅÔÅ ÐÒÉÏÂÒÅÓÔÉ ÎÁ ÓËÌÁÄÅ ÐÏ ÁÄÒÅÓÕ: ç. ÷ÌÁÄÉ×ÏÓÔÏË, ÕÌ.
> äÎÅÐÒÏÐÅÔÒÏ×ÓËÁÑ 19, ÓËÌÁÄ óÅ×ÅÒÏÔÏÒÇÁ, × Ò-ÎÅ. âÁÍÁ. ôÅÌÅÆÏÎ: 8(22)
> 46-72-89
> mail-to:[EMAIL PROTECTED]
> http://www.primrek.by.ru
>
>
------------------------------
From: [EMAIL PROTECTED] (Peter Harrison)
Crossposted-To: alt.sources.crypto,talk.politics.crypto
Subject: Encrypted Email for Business Documents
Date: Sat, 24 Feb 2001 00:39:08 GMT
Greetings,
I am developing a Open Source project to send business documents
across the Internet. Part of the system is a secure transmission
system based on email.
I am trying to solve some of the issues around what makes encryption
hard to use right now. For example, I want to imbed email addresses
of the sender and recipient. This will be used to look up servers to
obtain public keys (if a public key has not already been obtained for
the email address).
The idea is to make the encryption as invisible as possible. This way
I can make it easy to send business documents - such as invoices -
across the internet in reasonable security.
I am inviting everyone to take a look at my (rough) spec and comment
See the spec at: http://www.devcentre.org/email_spec.htm\
Comments are welcome to [EMAIL PROTECTED]
Regards,
Peter Harrison
------------------------------
From: "Stefan Habenschuss" <[EMAIL PROTECTED]>
Subject: Re: Freq analysis of a possible cyphertext.
Date: Sat, 24 Feb 2001 00:41:13 GMT
[snipped]
I think its random.... At least computing indeces of coincidence for
keylengths up to 400 gave me nothing over 0,06.
------------------------------
From: "Michael Scott" <[EMAIL PROTECTED]>
Subject: Re: MIKE alternative to SPEKE and PAK (long)
Date: Fri, 23 Feb 2001 18:36:26 -0600
To recap the aim is to log in to a server using a low entropy password P.
The server stores a verifier v=4^x mod p, where x=H(s,P), and s is "salt".
Anyone who steals a verifier should still have difficulty logging in without
knowing P.
The claimed advantage of this approach is that it works in both the SGSP
(Small Generator/Safe Prime) and POSG (Prime Order SubGroup) finite field
settings, and also with Elliptic curves. It is described in the SGSP
setting. It is based on Diffie-Hellman. The idea is to use two independent
generators, here we chose 3 and 4, which are both generators of the group of
size (p-1)/2 for p a safe prime. It is assumed that no-one can solve 3^y mod
p = 4.
Client Carol is logging in to Server Steve.
This version is much faster. A critical change in this version is that Steve
is now required to transmit a hash value containing the verifier in step 7
(as in PAK) before Carol sends anything useful. Therefore the values sent by
Steve can be trusted, and any attempt to masquerade as a false server is
foiled.
1. Carol sends username to Steve
2. Steve sends Carol the stored salt s, and looks up v.
3. Carol calculates x=H(s,P), and A=3^a.4^x mod p
4. Steve calculates B=3^b.4^r, and u=4^r (the El Gamal encryption of 3^b).
Exponents a, b and r are randomly chosen.
5. Carol sends A to Steve - if A=0 Steve aborts. Steve sends B and u to
Carol.
6. Carol calculates S=(B/u^x)^a and the key K=H(S). Steve calculates
S=(A/v)^b and the key K=H(S).
7. Steve sends Carol M1=H(S,v). Carol checks it against H(S,4^x) and aborts
if it is wrong.
8. Carol sends Steve M2=H(M1,S,B/u^x,4^x). Steve checks it against
H(M1,S,3^b,v) and aborts if it is wrong.
Let Tg be the time required for a known-base exponentiation, Tb be the time
for an unknown base exponentiation, and Td be the time required for a double
exponentiation, then this protocol requires 2Tg+2Tb for each side.
However we can do a little better. By requiring Steve to also check that
A!=+v or -v in step 5, it appears that B/u^x need not be included in M2,
which brings the client side computation down to 2Tg+Td. In this case in the
POSG setting it is important that p be a so-called Lim-Lee prime, so that no
other small order sub-groups exist, otherwise Chris who doesn't know x but
does know v might log in by sending A=w.v, where w is of low order.
It is further observed that r apparently need not be as large as a and b,
which might be used to reduce the server side computation. It needs only be
large enough so that finding r from 4^r is as difficult as finding x from v.
Mike Scott
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Super strong crypto
Date: Sat, 24 Feb 2001 00:49:38 GMT
Douglas A. Gwyn wrote:
>
> wtshaw wrote:
> > Considering what was in the public eye at the time, it was the best
> > thing going, but I was after bigger game long before that, and I was
> > on the right track. Too many people forget Shannon, that the amount
> > of ciphertext necessary for breaking a cipher is a critical part of
> > strength.
>
> I think it's not forgotten, just the designers don't know how to use
> it.
>
> Here is a "straw man" block cipher design for you all to analyze:
> The last PT block before the unicity distance is reached contains
> a newly generated random key to replace the one currently in use.
> It's a new form of "chaining" mode, if you wish.
Hmm. Unless I'm mistaken, one needs only 2 or 3 blocks of known
plaintext for brute force to work on DES. This is that cipher's unicity
distance. Does anyone besides me see this as a problem with this "straw
man" idea?
Maybe you mean something besides unicity distance?
Perhaps you would suggest that, for DES, one use any one key for no more
than 2^48 blocks, since that is (AFAIK) the smallest number of blocks
needed for linear or differential analysis to get the key?
So what do you do for ciphers which don't have weaknesses like that?
--
A solution in hand is worth two in the book.
------------------------------
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: [OT] Re: Really big numbers in C
Date: Sat, 24 Feb 2001 01:07:58 GMT
Michael Scott wrote:
> Also
>
> Crypto++
> Cryptlib
>
> BTW 4096 bit numbers are just big. Really big would be 1 million bits and
> up.
Only for those who feel better measuring their members in angstroms.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Simple, possibly flawed, stream cipher
Date: 24 Feb 2001 01:20:52 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Benjamin Goldberg wrote:
>uint8 state[8] = { key };
>uint8 sbox[256];
>
>for( i = 0, x = 1; i < 8; ++i )
> x ^= sbox[ state[i] += (x>>i) & 1 ];
>keystreambit := x;
>
>One nice thing I can see about this, though: By unrolling and
>pipelineing, it should take one clock cycle per byte of output.
How do you figure you get one clock cycle per byte?
Looks like 8 iterations of the loop per keystream byte, no?
Do you mean that x is always initialized to 1 before each
8 iterations of the loop? If so, the state-update function
appears to be non-bijective, so you lose a little bit of information
at each step, and probably you fall into a cycle within about 2^32
outputs.
Is the S-box intended to be public? If so, 64 bits of state
space isn't enough to prevent time-space tradeoff attacks.
------------------------------
Date: Sat, 24 Feb 2001 01:25:20 +0000
From: Kat Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: question1,2,2a,3,4,5,5a,5b,5c,6
=====BEGIN PGP SIGNED MESSAGE=====
h4jiwk9j wrote:
> 5.My user name is the encryption of my dog's name.
Your dog's name is Benjamin. Does that answer question 5? :-)
- --
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
iQEVAwUBOpcNWzkCAxeYt5gVAQH9DQf9FezoTHbUU4Zx1qBmmyNB+cwNL//DE/bU
P9T1qvoP6eYM8Xx420NlRwNCjK0pO/Org+ntBQvq3aUoKdp5Br6FIAPQD3Qp48pf
iA8mF3gi4iOsk4cI5idzcblEQTZk7/InceDwzHABVWE/xmhYTa1gwAHj+EI+V4Om
kRGiY1rq28PpV3qJwB53KbUeWPPQmiWcLb4ISF3p1Zxl6VGajoB3BDsoMZoQEm0b
L/4LZS4gnps2cvB5CTU5CK1mDi3DX6TFu/mTQNUfQR8II0yPLP46C3UIE7B1EK1h
IDSfgID2c8tlswENZGp1q095D8hZ2zTcfpf/FC9heAfn/oeocP1QZg==
=Tf3Y
=====END PGP SIGNATURE=====
------------------------------
Date: Sat, 24 Feb 2001 01:27:55 +0000
From: Kat Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Processing on cyphertext
=====BEGIN PGP SIGNED MESSAGE=====
Ian Woods wrote:
> Is anyone aware of any encryption schemes which allow some (restricted)
> forms of processing on cyphertext? To make a bit more sense...
>
> E(num1,key) * E(num2,key) = E(num1*num2,key)
>
> Or in English: performing an operation on two encrypted numbers (num1 and
> num2) creates a new cyphertext which when decrypted is the value of the
> operation performed on num1 and num2.
The RSA trapdoor function has this property (for multiplication modulo
the modulus, N):
num1^e * num2^e = (num1*num2)^e (mod N)
However, be very careful - the RSA trapdoor function is not secure on its
own as an encryption scheme (without using an encoding method, which
would destroy the multiplicative property). That doesn't mean you can't
use it, but its security will have to be analysed in the specific context
of whatever protocol it is being used in. What exactly is the application?
- --
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
iQEVAwUBOpXZWzkCAxeYt5gVAQE0iAf/dAcF4qJTNarg9a+X14Efa0xBPEup+Ei6
xKWbkk1TqW/aAFVkdXRr8Rd5j9lMiTHBXycACdxw/j5z8zcyX6l0GB0c4kL5HamL
wkEgkkcXBG/02Ku7kEolRIxnuSKivxUJJgrGku7P4yfiwTkPz+xD4fxk5583rmB8
XMBVQqta+RlHUUf8DGKeYXPJMM1Ogch3XRCNgGZpNpJ9ZvybEharEwRrcOi5Lw67
z/e9q4MSAeSxb+cb+0VBWdAOTrRriE6l6ejVufV1J0lbuk+tFcLCgxabT2AcLeWg
XHcjU2IqINooi9qVFEg8HJBchcOwlO9+Mx0Pw952TRO0CpXbZXw8Zw==
=PJVe
=====END PGP SIGNATURE=====
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Simple, possibly flawed, stream cipher
Date: 24 Feb 2001 01:45:59 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Benjamin Goldberg wrote:
>uint8 state[8] = { key };
>for( i = 0, x = 1; i < 8; ++i )
> x ^= sbox[ state[i] += (x>>i) & 1 ];
>keystreambit := x;
Ahh, here's a totally deadly attack. It is based on a
self-synchronization property combined with a total lack of avalanche
from state[i] to state[i-1].
Let S denote the state before the state-update function, and S' denote
the state afterwards. Suppose I start with a guess G at the state, and
run the state-update function on G to get G'. Note that if G agrees
with S in the first N positions, then G' will necessarily agree with
S' in the first N positions, too. Moreover, with probability 1/256,
we will have G'[N] = S'[N]. In other words, if G agrees with S in
the first N positions, then G agrees with S in the first N positions
(255/256 of the time) or the first N+1 positions (1/256 of the time).
This is a self-synchronization property.
Imagine if I just start with a completely random initial guess G_0 and
apply the state-update function to it to get a sequence G_0,G_1,G_2,...
After about 256 iterations, I expect G_i to agree with S_i in about 1
position, and once they agree in the first position, they'll agree in
that position forever. After 256*k iterations, they'll agree in about
k positions.
So, pick a random key. Then, after about 4000 or so outputs, the
keystream will be completely independent of the key value!
This means that the proposal appears to be completely insecure, if I
did not make any mistakes in my analysis.
------------------------------
From: Bob Day <[EMAIL PROTECTED]>
Subject: Re: Really big numbers in C
Date: Sat, 24 Feb 2001 01:58:57 GMT
Taylor Francis wrote:
> Anyone know how to handle really bug numbers in C? I'm talking
> 1024-4096 bit numbers...my compiler only handles 64 bit (that I can
> tell...)
Windows or Unix-Linux?
-- Bob Day
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Really big numbers in C
Date: Fri, 23 Feb 2001 14:21:42 -0800
Yeah go to your favorite search engine and search for BIGNUM libraries. Some
of the most commonly recommended ones on here are:
GMP
openssl
LiDIA
MIRACL
Take your pick, they're all great.
Joe
"Taylor Francis" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Anyone know how to handle really bug numbers in C? I'm talking
> 1024-4096 bit numbers...my compiler only handles 64 bit (that I can
> tell...)
>
> Thanks
------------------------------
From: "Henrick Hellström" <[EMAIL PROTECTED]>
Subject: Re: Simple, possibly flawed, stream cipher
Date: Sat, 24 Feb 2001 03:22:01 +0100
Let's see if I got the pseudo code right:
j.1. LET x := 1.
j.2. FOR i := 0 TO 7 DO:
j.2.1. IF (x shr i) IS ODD THEN LET state[i] := state[i] + 1.
j.2.2. LET x := x XOR sbox[state[i]].
j.3. LET k[j] := x.
Firstly, I'd like to know if result is a one bit or an eight bit value.
Since x is to be a byte, "keystreambit" appears to be a typo.
Assuming that result is a byte, I'd go about attacking this stream cipher
using a differential attack, based on the assumption that sbox is key
independent and known, and on the fact that state[0] is always incremented
and that state[1],...,state[7] are incremented with a probability of 0.5 and
otherwise unchanged.
Let y[j] be the number such that, at step j.2.1 and for each i, (x SHR i) is
odd if and only if (y[j] SHR i) is odd. Now, for each pair k[j], k[j +1],
there are exactly 2**(7 + 8) possible expressions
z = b0 * (sbox[s0] XOR sbox[s0+1]) XOR ... XOR b7 * (sbox[s7] XOR
sbox[s7+1]),
such that b0 = 1. We are only interested in those such that z = (k[j] XOR
k[j+1]), because if y[j+1] = b0 + b1 * 2 + ... + b7 * 128 and (at step
j+1.3.) s0 = state[0], s1 = state[1], ... , s7 = state[7], then z = (k[j]
XOR k[j+1]). Find these combinations for a sequence of k[j]'s, engage in
some not too complicated puzzle solving, and you will end up with the
initial value of state[0],...,state[7].
--
Henrick Hellström [EMAIL PROTECTED]
StreamSec HB http://www.streamsec.com
"Benjamin Goldberg" <[EMAIL PROTECTED]> skrev i meddelandet
news:[EMAIL PROTECTED]...
> I've thought about this idea for the last couple of days, and I haven't
> yet figured out what kind of weakness(es) it has.
>
> uint8 state[8] = { key };
> uint8 sbox[256];
>
> for( i = 0, x = 1; i < 8; ++i )
> x ^= sbox[ state[i] += (x>>i) & 1 ];
> keystreambit := x;
>
> I can't help but think that there's got to be a flaw here somewhere,
> since it's so simple, but I can't see where.
>
> Also, I'm not quite certain what properties sbox should have --
> especially if I want the cipher to have the maximum period.
>
> One nice thing I can see about this, though: By unrolling and
> pipelineing, it should take one clock cycle per byte of output.
>
> --
> A solution in hand is worth two in the book.
------------------------------
From: "Henrick Hellström" <[EMAIL PROTECTED]>
Subject: Re: super-stong crypto, straw man phase 2
Date: Fri, 23 Feb 2001 14:20:00 +0100
--
Henrick Hellström [EMAIL PROTECTED]
StreamSec HB http://www.streamsec.com
"Henrick Hellström" <[EMAIL PROTECTED]> skrev i meddelandet
news:975j63$ce2$[EMAIL PROTECTED]...
> Yes, and all I stated was that there was a limit to the extent your mode
> would foil known-plain text attacks.
>
> If a brute-force search is impossible in some respect, the security is
> unlimited in that same respect. For instance, the brute-force attack I
> outlined only works in a forward direction. It cannot be rewinded(*), so
the
> plain-text transmitted prior to the first block of known plain-text will
> remain an absolute secret to this particular attacker, given his knowledge
> and that he mounts a known plain-text attack, but regardless of the
software
> and hardware at his disposal.
>
> (*) I.e. provided that the batches are large enough relatively the size of
> the keys, so that the set K of keys the attacker will find epistemically
> possible to have been used to encrypt the last unknown plain-text, is such
> that there exists at least two different keys in K corresponding to
> different and sufficiently plausible plain-text.
>
> --
> Henrick Hellström [EMAIL PROTECTED]
> StreamSec HB http://www.streamsec.com
>
> "Douglas A. Gwyn" <[EMAIL PROTECTED]> skrev i meddelandet
> news:[EMAIL PROTECTED]...
> > "Henrick Hellström" wrote:
> > > ... brute-force attacks are theoretically possible:
> >
> > I didn't consider it necessary to stipulate that the key
> > size would be chosen large enough to prevent brute-force
> > search of the key space; we generally take that for granted.
>
>
>
>
------------------------------
From: "Brian McKeever" <[EMAIL PROTECTED]>
Subject: Re: __(?) MATRIX version of Fermat's Little Theorem
Date: Fri, 23 Feb 2001 19:05:08 -0800
"kctang" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> We know that a^(p-1) = 1 mod p, where p is a prime, and p does not
> divide a.
>
> Is there a *Matrix* version of Fermat's little theorem? (e.g.
> mod p taking element-wisely, what is the index?)
There is something similar, but not nearly as useful. The essence of that
statement is that for a group G and any element g of G, g^|G| = identity
(order of multiplicative group of GF(p) is p-1). In these terms, it
obviously also applies to matrices. Here's the catch: Your group is going
to be *invertible* n by n matrices (so the determinant != 0 mod p), and
you'll have to figure out how many of those there are in terms of n and p.
I don't know the formula off the top of my head, but if you're still
interested, it should make for a decent exercise.
Brian
------------------------------
** 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
******************************
