Cryptography-Digest Digest #247, Volume #12 Wed, 19 Jul 00 13:13:00 EDT
Contents:
Re: Crypto source code library suggestions? (Daniel Leonard)
telephone encryption. ("George Gordon")
Re: Questions!!!! ("George Gordon")
Re: Carnivore and Man-in-the-middle (John Savard)
Re: how strong is my own encryption? (John Savard)
Re: Good free stream cipher ? (Runu Knips)
Re: RC4-- repetition length? (Guy Macon)
Re: WSJ Article on Mexico / Encryption (Guy Macon)
Re: Good free stream cipher ? (Paul Koning)
Re: how strong is my own encryption? (Paul Koning)
Re: Good free stream cipher ? (Runu Knips)
Small subgroup attacks (was Re: Has RSADSI Lost their mind?) (David Hopwood)
Re: Questions!!!! (Mark Wooding)
Books ("Neil Hendrick")
VCR+ ([EMAIL PROTECTED])
Re: PGP US Versions Broken,no good?? (Mark Wooding)
Re: Books (Mark Wooding)
Re: Questions!!!! ("George Gordon")
----------------------------------------------------------------------------
From: Daniel Leonard <[EMAIL PROTECTED]>
Subject: Re: Crypto source code library suggestions?
Date: Wed, 19 Jul 2000 13:17:34 GMT
On Tue, 18 Jul 2000, Kirk Ellett wrote:
> Hello,
>=20
> I am in need of a non-platform dependent encryption library in ANSI C
> source code. I only need conventional strong encryption/decryption, not
> public key, key management, or compression. The most important
> requirements for my project are speed and a generic code base, one not
> dependent on any libraries other than standard C. I also need it in a C
> library API format, not a standalone executable. Can anyone point me to
> any publicly available code legal for use in the US?
>=20
> Kirk
>=20
Most reference implementations only use standart C. If you remove their
main(), only small adjustment are required. But then there might be
copyright issues to that solution.
==========
Daniel L=E9onard
OGMP Informatics Division E-Mail: [EMAIL PROTECTED]
D=E9partement de Biochimie Tel :
Universit=E9 de Montr=E9al Fax :
Montr=E9al, Quebec Office: Pavillon Principal G-312
Canada H3C 3J7 WWW :
------------------------------
From: "George Gordon" <[EMAIL PROTECTED]>
Subject: telephone encryption.
Date: Wed, 19 Jul 2000 09:22:30 -0400
Hi,
I saw a telephone encryption device in the August North American edition of
Popular Science. Page 24. The device called Privatel is made by L-3
Communications. It says it uses 168-bit encryption. I am in no way
associated with this company. My question is: 3DES? Key-Escrow??
George
------------------------------
From: "George Gordon" <[EMAIL PROTECTED]>
Subject: Re: Questions!!!!
Date: Wed, 19 Jul 2000 09:29:27 -0400
George Gordon wrote in message ...
>1) I read in the literature that impossible differentials can be found for
>*any* Feistel cipher for up to 5 rounds. (Schneier, Biham) My question is
>how is that possible for a design like Karn, MDC, etc where one side is a
>full hash? ie: 5-round Karn. It doesn't make sense to me.
>
In Schneier's Twofish literature, it states that the five-round impossible
differential works if the round function is invertible. OK, any Feistel
round is invertible. Also, any F-function is invertible if computed as an
S-box. Can readers clarify this for me :) Please forgive my ignorance, I'm
not a guru!
George
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Carnivore and Man-in-the-middle
Date: Wed, 19 Jul 2000 13:33:30 GMT
On 17 Jul 2000 17:34:48 GMT, [EMAIL PROTECTED]
wrote, in part:
> Reading about it made me think about the "Man in the Middle" attack
>against public key cryptosystems.
The man-in-the-middle attack is dangerous, because there is always the
chance of getting caught if keys are checked by another route. Also,
most programs that use public-key cryptography over the Internet use
key certificates to defeat this attack.
John Savard (teneerf <-)
Now Available! The Secret of the Web's Most Overused Style of Frames!
http://home.ecn.ab.ca/~jsavard/frhome.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: how strong is my own encryption?
Date: Wed, 19 Jul 2000 13:31:30 GMT
On Wed, 19 Jul 2000 08:53:15 GMT, [EMAIL PROTECTED] wrote, in part:
>I somehow process all the text adding to each letter (ASCII code)
>a password char (ASCII code) (every time it's the next char, and
>I do the loop).
This is a version of the Vigenere cipher. However, using ASCII
characters weakens it further, since you are using an alphabet that
contains many characters, in stretches, that are seldom used (i.e.,
nonprintable ones).
However, it is a start; combined with other methods it can be useful.
John Savard (teneerf <-)
Now Available! The Secret of the Web's Most Overused Style of Frames!
http://home.ecn.ab.ca/~jsavard/frhome.htm
------------------------------
Date: Wed, 19 Jul 2000 15:27:12 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: Good free stream cipher ?
"S�bastien SAUVAGE" wrote:
> [EMAIL PROTECTED] (Runu Knips) wrote in <[EMAIL PROTECTED]>:
> >I'm looking for a good & free stream cipher algorithm.
> >Does anybody have a suggestion ?
>
> I think ISAAC would fit.
> Free, long period, large seed and large internal state,
> uniformly distributed and unbiased, reasonably fast.
Hmm thank you looks interesting unfortunatley it seems
this algorithm had not received much analyis yet. :-)
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: RC4-- repetition length?
Date: 19 Jul 2000 10:50:13 EDT
Runu Knips wrote:
>The I/O is _NOT_ the part of the algorithm, or the
>implementation of the algorithm. It is of course
>part of the final program; but it can't change the
>data (except doing things like base64 encode etc).
Got it. You are using definitions of "implementation" and "final
program" that differ from mine. I will assume that my definitions
(which are as used in embedded systems programming) are not appropriate
here and that your reflects common usage in the crypto community.
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: WSJ Article on Mexico / Encryption
Date: 19 Jul 2000 10:58:55 EDT
jungle wrote:
>
>
>http://www.wired.com/news/politics/0,1283,37337,00.html
>
>Mexico Race Hinges on Code Crack by Mike Kamber
> 3:00 a.m. Jun. 30, 2000 PDT
>
> "The [password] we don't have contains 11 characters -- eight letters and
> three numbers," he said. "So there are millions of combinations -- it
> could take time to find it."
>
BWAAAHAAAHAAAHAAAA!!!!!
I can't stand it. Stop. You're killing me. Let me catch my breath.
<chuckle> <more wild, uncontrollable laughing> <faints>
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: Good free stream cipher ?
Date: Wed, 19 Jul 2000 10:30:53 -0400
Runu Knips wrote:
>
> I'm looking for a good & free stream cipher algorithm.
How about any good block cipher in counter mode, or CFB mode?
Or are you looking for something different for some
reason?
paul
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: how strong is my own encryption?
Date: Wed, 19 Jul 2000 10:37:20 -0400
[EMAIL PROTECTED] wrote:
>
> Hi everybody!
>
> I may sound like an idiot, looking at all the algorithms here and
> there, I'm sure my algorithm isn't something, anyway here's the
> question:
>
> How long would it take to crack down this type of encryption
> (suppose you have the source code of the encryption software):
>
> There is some kind of password (5 to 8 chars), I want to encrypt
> a simple text file (in English). And here's what I do:
>
> I somehow process all the text adding to each letter (ASCII code)
> a password char (ASCII code) (every time it's the next char, and
> I do the loop).
>
> For example:
> if the original text is:
> "A little dog is in here!"
> (ASCII codes: A=65, space=32, l=108, i=105 and so on...)
>
> and the password is:
> "dog"
> (ASCII codes: d=100, o=111, g=103)
>
> algorithm will do this thing:
> "65+100 32+111 108+103 105+100..." and so on....
> (A+d , " "+o , l+g , i+d ....)
>
> the encrypted file will look like:
> "165 143 211 205..." and so on....
With typical plaintext of a line or more, a few minutes
by hand. With the plaintext you gave, a bit longer because
it has unusual letter frequencies. (Incidentally, keeping
the spaces makes it easier.)
> (Note: there is no way the cracker will know the original password,
> unless he/she figures it out)
>
> and here's another question, what if I increase the password from
> 5 to 8 chars to let's say 20 chars, will it help or not?
Not to speak of. It increases the amount of ciphertext needed
proportionally. If you encrypt, say, 5 lines of text with a
key that long, it still takes only a few minutes manual labor
to recover the key and the ciphertext.
What you describe is the Vigenere system, popular in the
19th century, and also broken back then. Read all about it
in David Kahn's "The Codebreakers" (highly recommended,
provided it's the hardcover).
paul
--
!-----------------------------------------------------------------------
! Paul Koning, NI1D, D-20853
! Lucent Corporation, 50 Nagog Park, Acton, MA 01720, USA
! phone: +1 978 263 0060 ext 115, fax: +1 978 263 8386
! email: [EMAIL PROTECTED]
! Pgp: 27 81 A9 73 A6 0B B3 BE 18 A3 BF DD 1A 59 51 75
!-----------------------------------------------------------------------
! "A system of licensing and registration is the perfect device to deny
! gun ownership to the bourgeoisie."
! -- Vladimir Ilyich Lenin
------------------------------
Date: Wed, 19 Jul 2000 17:21:16 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: Good free stream cipher ?
Scott Fluhrer wrote:
> Boris Kazak <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > Runu Knips wrote:
> > > I'm looking for a good & free stream cipher algorithm.
> > > Does anybody have a suggestion ?
> > -------------------------
> > Recipe: Take BLOWFISH and run the key setup procedure.
> > You will have 5 arrays of subkeys.
> > P[72], S0[1024], S1[1024], S2[1024], S3[1024]
> > Now your stream cipher will look like following:
> > Ct[i] = Pt[i]^P[i%71]^S0[i%1019]^S1[i%1021]^S2[i%1023]^S3[i%1024]
> > (you can verify yourself that 71, 1019, 1021, 1023 and 1024 are
> > all mutually prime)
> > The period of this generator will be equal to the product of
> > all 5 numbers = 77380915780608 ~ 2^46.
Not much for a random generator which requires more than 4KB
of data, isn't it ?
> And this can be broken (that is, you can reconstruct the array contents that
> the stream cipher uses) with 71+1019+1021+1023+1024 = 4158 known stream
> cipher outputs, by Gaussian elimination.
Congratulations !
Funny, I thought about a concept which used mutually prime sized
arrays at home. Using a avalanche addition and extracting the
bits piece by piece using the parity() function should lead to a
good stream cipher, doesn't it ? However, I fear its pretty slow.
------------------------------
Date: Wed, 19 Jul 2000 04:09:47 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Small subgroup attacks (was Re: Has RSADSI Lost their mind?)
=====BEGIN PGP SIGNED MESSAGE=====
"David A. Wagner" wrote:
> In article <[EMAIL PROTECTED]>,
> David Hopwood <[EMAIL PROTECTED]> wrote:
> > Am I not correct in thinking that it's OK to re-use DH keys iff it is
> > checked that all transmitted group elements are of large order?
>
> No, it's not sufficient for them to have large order.
>
> Consider the Lim-Lee attack: Alice sends g^a, Mallet changes this
> to - g^a (which has large order), Bob computes (- g^a)^b, and uses
> this as his shared key; Bob sends g^b, Alice computes (g^b)^a, and
> uses this as her shared key. This discloses a bit of information
> on b, since key transfer succeeds iff b is even. At least, I _think_
> this is the Lim-Lee attack, anyway; I didn't double-check, and I
> could be wrong.
Yes, one bit of information is lost. For p of the form given below,
that's all that is lost, though, and it is always the same bit for
any given b - i.e. whether b is even or odd. That still leaves more
than sufficient uncertainty in b to prevent square-root attacks. If
the DH agreed value is used as the input to a hash or PRF (as it is
in SSL/TLS), I don't see any vulnerability arising from this.
You're right that it is not the checking of the order that is
important to prevent Lim-Lee attacks, it is the structure of p-1.
However, it's still necessary to check that the order is not small,
to ensure that the agreed value is not forced into a small set.
> You should check that all transmitted values are in the subgroup,
> not just that they have large order.
>
> > For p = 2qR + 1 with q and R prime, that can be very cheap, since if
> > y is a transmitted value, it's sufficient to check that 2 <= y <= p-2.
>
> I don't think this is correct either. If R is small, then y = g^{2q}
> is a counterexample.
The context was that q is just large enough to prevent square-root
attacks (say 180-256 bits), and p should be >= 1024 bits to prevent
index-calculus-based attacks, in which case R cannot be small. I should
have made that clearer, though.
> But in any case, checking for large order is not enough.
>
> A trick that is useful: In some protocols, instead of checking that
> the transmitted value is in the subgroup, one can force it into the
> subgroup. E.g., instead of checking that y is in the order-q subgroup,
> simply compute y' = y^{2R}, and use y' in all subsequent computations.
> One need merely check that 1 < y' < p-1, and then one can be sure that
> y' is a non-trivial element of the q-order subgroup.
Yes, that's called "incompatible cofactor multiplication" [*] in RFC 2785
and IEEE P1363. It isn't compatible with any of the SSL/TLS ciphersuites,
unfortunately.
[*] "multiplication" rather than exponentiation, because it is more
often used with elliptic curve DH, although it's applicable to any
group.
- --
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
iQEVAwUBOXRx0DkCAxeYt5gVAQE3Kwf/RqBmoj9uDCwpXDma4krLDGgbEpghbUM/
qTGY9PmBTyV/wP7CF2wMlIBydxHVl30Gu9fwSPVlcdO0szXuyJZdzblZQgn+GETR
obHoIY8ehp03NhvmKoZbAitkh++Brf6eIgwrzoC8q2sB6F5HQUXp7NF8xeQ/91oR
oPUa+SJ/Vxmm27IZM/q27PfqHA0n+P9GyxNTMqD0j8RlBdAY4B9yX2HYPBlqSUfI
8Ly7429xuf6Lj8nz+qJae4q7hNF4ikV4KpQ+U+h/HSygcnGfTC6rPBHVPdLZWBnn
+P52jmcS2zy6LzAM5z/c4Kc4UGg8bL31xHwqOc8Dm0SPMNYGE8F5Hg==
=hZhk
=====END PGP SIGNATURE=====
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Questions!!!!
Date: 19 Jul 2000 15:30:38 GMT
George Gordon <[EMAIL PROTECTED]> wrote:
> In Schneier's Twofish literature, it states that the five-round
> impossible differential works if the round function is invertible.
I think this refers to the F-function, not the round function, which is
(x', y') = (y, x XOR F(y)). An F-function doesn't have to be
invertible, although there's a risk of good 2-round iterative
differentials if it's not:
0 d [Assume d != 0]
| |
|---[F]->(+) [0 ---> 0 for any function]
| |
0 d
| |
(+)<-[F]---| [d ---> 0 with probability p != 0]
| |
0 d
Hence we have (0, d) ---> (0, d) for two rounds with probability p.
This is the structure of Biham and Shamir's attack on DES.
> OK, any Feistel round is invertible.
Yes, but that's not what's being talked about.
> Also, any F-function is invertible if computed as an S-box.
Eh? Not all S-boxes are invertible. DES's aren't, for instance.
Neither is Blowfish's.
Let P be any injective function. Then for any nonzero input difference
d we have the impossible differential d -/-> 0 for P.
If F_i is any collection of random functions, then the Feistel network
constructed by the rules:
x_{i + 1} = y_i XOR F_i(x_i)
y_{i + 1} = x_i
has additional characteristics if iterated three or fewer rounds.
(Here, ---> denotes a differential with probability 1, and -/-> denotes
a differential with probability 0, i.e., an impossible differential; d
is any input difference, and d' is an arbitrary output difference.)
1: (0, d) ---> (0, d)
2: (0, d) ---> (d, d')
3: (0, d) -/-> (0, d') for d' != d
With more rounds than that, we only get d -/-> 0, which we expect from
any block cipher.
If we further constrain the F_i to be permutations, we have a more
interesting family of characteristics (in addition to the ones above).
It's more interesting (and edifying) to trace the evolution of these in
detail.
0 d [Assume d != 0]
| |
|---[F]->(+) [0 ---> 0 for any function]
| |
0 d
| |
(+)<-[F]---| [d -/-> 0, so d_1 != 0]
| |
d_1 d
| |
|---[F]->(+) [d_1 -/-> 0 too, so d_2 != d]
| |
d_1 d_2
| |
(+)<-[F]---|
| |
d_3 d_2
| |
|---[F]->(+)
| |
d_3 d_4
Note that, if d_3 = 0, d_4 = d_2, and we know d_2 != d. Hence we have
the 5-round impossible differential
(0, d) -/-> (0, d)
This I believe to be the only one. I did exhaustive testing on a large
collection of small Feistel networks based on random functions and
random permutations, and the above characteristic was all that was left,
except for d -/-> 0.
-- [mdw]
------------------------------
From: "Neil Hendrick" <[EMAIL PROTECTED]>
Subject: Books
Date: Wed, 19 Jul 2000 15:30:51 GMT
Lets say you wanted to sell e-books in a format where people could easily
download it, paying for it online, then read it on their computers, even
print it, but they would be unable to distribute it. My thought is a reader
program that would display simple text onscreen, would send text to printer,
but would only save to disk in an encrypted format. They would hold a key
unique to their machine, allowing only one-ticket-one-seat use.
Ideas?
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: alt.video.vcr,alt.2600
Subject: VCR+
Date: Wed, 19 Jul 2000 15:35:52 GMT
Is there any publicly available software tool that can generate the
VCR+ code?
Bon.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Crossposted-To: alt.security.pgp
Subject: Re: PGP US Versions Broken,no good??
Date: 19 Jul 2000 16:17:23 GMT
Richard Herring <[EMAIL PROTECTED]> wrote:
> This doesn't work. In its public-key modes, The random session keys
> will be different each time, and so will the output ciphertext,
> for the same input, even when nothing is broken.
Indeed. In fact, the public-key crypto is randomized too. PGP versions
later than 2.3 (I think) use PKCS#1 padding for RSA, which takes a
message M and pads it out like this:
00 || 02 || ... random nonzero padding ... || 00 || M
so that it's the same length as the RSA modulus. (Previous versions did
something similar, but the various bits were in a different order.
There's no particularly good reason for the change.)
Diffie-Hellman (actually ElGamal, for some stupid reason) encryption is
inherently randomized anyway.
So, almost none of the two PGP-encrypted messages will be the same at
all.
However, note that RSA *signatures*, as PGP implements them, are
deterministic: given the same input they'll give the same output. In
particular, the (PKCS#1) padding applied is like this:
00 || 01 || ... FF FF FF ... || 00 || ... DER goop ... || H(M)
where the DER goop is fixed and uninteresting. However, PGP-signed
messages contain timestamps, so you must ensure that your two signings
occur simultaneously (to the second). However, it's probably better to
have a trusted program which dissects RSA signatures and shows you the
contents of everything, confirming that it's OK.
DSA signatures are randomized. It's not possible to be sure, just by
looking at a signature, that it doesn't contain a subliminal channel
which (say) leaks bits of your secret key. You must audit your PGP
source.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Books
Date: 19 Jul 2000 16:26:52 GMT
Neil Hendrick <[EMAIL PROTECTED]> wrote:
> Lets say you wanted to sell e-books in a format where people could
> easily download it, paying for it online, then read it on their
> computers, even print it, but they would be unable to distribute it.
No. Impossible.
[Attack: set your printer driver to print PostScript to a file, and then
print the document. Distribute copies of the PostScript file to your
friends, telling them where to get the Ghostscript viewer.]
> My thought is a reader program that would display simple text
> onscreen, would send text to printer, but would only save to disk in
> an encrypted format. They would hold a key unique to their machine,
> allowing only one-ticket-one-seat use. Ideas?
No.
1. You can't bind a key to a machine that well and still expect users
to be happy when they upgrade their hardware. There's no part of a
computer which users won't want to replace at some point. And
users (and administrators) hate dongles.
2. [The clincher.] The key must be available to the reader program.
It must therefore be available to any other program which does the
same thing as the reader to find the key. This other program can
decrypt the files and write out the plaintext.
3. [Icing on the cake.] I can grab the text off the screen as
bitmaps. I can even write a program to automatically scroll your
window, grabbing and compressing bitmaps as it goes.
Do yourself a favour: forget it.
-- [mdw]
------------------------------
From: "George Gordon" <[EMAIL PROTECTED]>
Subject: Re: Questions!!!!
Date: Wed, 19 Jul 2000 12:49:14 -0400
>> Also, any F-function is invertible if computed as an S-box.
>
>Eh? Not all S-boxes are invertible. DES's aren't, for instance.
>Neither is Blowfish's.
>
I didn't refer to the actual S-boxes in a cipher. I simply meant that if you
look at the structure as a whole. In this case, a 32-bit half. The half
should be as bijective as possible. (I would think)
>Note that, if d_3 = 0, d_4 = d_2, and we know d_2 != d. Hence we have
>the 5-round impossible differential
>
> (0, d) -/-> (0, d)
>
>This I believe to be the only one. I did exhaustive testing on a large
>collection of small Feistel networks based on random functions and
>random permutations, and the above characteristic was all that was left,
>except for d -/-> 0.
>
>-- [mdw]
Thanks, very informative.
George
------------------------------
** 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
******************************
