Cryptography-Digest Digest #314, Volume #12 Sun, 30 Jul 00 06:13:01 EDT
Contents:
Re: Elliptic Curves encryption (Roger Schlafly)
Re: Reference to a public key technique in NYTimes (David A Molnar)
Re: How is the security of Outlook Express encryption ? (Edward A. Falk)
Re: substring reversal (Edward A. Falk)
Re: Enigma with Transpostion (German Mechanisation) (John Savard)
Re: Proving continued possession of a file (David Hopwood)
Re: How is the security of Outlook Express encryption ? (Guy Macon)
Re: Bluetooth security source code (Samuel Paik)
Re: The Purple Cipher (World War II) (John Savard)
Re: Re: PGP US Versions Broken,no good?? (Edward A. Falk)
Re: counter as IV? ("Douglas A. Gwyn")
Re: A naive question ("Douglas A. Gwyn")
Re: How secure is Pegwit? (Mack)
Small block ciphers (Mack)
Re: Small block ciphers (Mack)
Re: Randomize, RandSeed and PRNG (Tim Tyler)
Re: Enigma with Transpostion (German Mechanisation) (Mok-Kong Shen)
Re: Randomize, RandSeed and PRNG (Daniel)
Re: Randomize, RandSeed and PRNG (Daniel)
Re: Proving continued possession of a file ([EMAIL PROTECTED])
Re: Small block ciphers (Mok-Kong Shen)
----------------------------------------------------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: Elliptic Curves encryption
Date: Sat, 29 Jul 2000 15:24:11 -0700
Jerry Coffin wrote:
> With RSA, things would be completely different: I'd simply show how
> much more difficult it is to factor a number than to find a couple of
> primes and multiply them together.
That tells them that one particular attack fails if factoring
is hard. That's all. It doesn't directly say anything about
the security of RSA because the RSA problem might be easier
than factoring.
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Reference to a public key technique in NYTimes
Date: 29 Jul 2000 22:10:23 GMT
John Bailey <[EMAIL PROTECTED]> wrote:
> Can someone point me to prior discussion of this technique?
> Are there accessible background references?
The public key cryptosystem is NTRU. The rest of this message
will refer to the cryptosystem, as I don't know anything about its
application to digital rights management.
NTRU is a company now with funding from Sony and others.
http://www.ntru.com/
The web site has some nice pointers to papers on the system and
current attacks. If you can find the NTRU Technical Center page, you
can get your hands on the Algorithmic Number Theory Symposium III
paper which formally introduced NTRU, although the scheme had apparently
been known since a presentation at the rump of Crypto '96.
The site also has a survey of related literature which includes pointers
to papers detailing the best current attacks on NTRU.
I haven't read all the latest attack papers yet, so I'm going to
refrain from commenting on "the security of NTRU."
Probably best to do is to go to the site and click on the link
about "summaries of papers" or use the search facility to get directly
to the Technical Center. The rest of the site is the usual marketing
stuff. :)
Many of the papers are technical conference submissions, so your call on
whether they're "accessible." The NTRU people also have some nice
tutorials on how the system works designed for those of us without phds.
I think NTRU was discussed here previously and on the [EMAIL PROTECTED]
mailing list. You can check deja for sci.crypt archives; don't know
where mailing list archives are.
-David
------------------------------
From: [EMAIL PROTECTED] (Edward A. Falk)
Subject: Re: How is the security of Outlook Express encryption ?
Date: 29 Jul 2000 23:26:57 GMT
POP3 has a secure authentication method, but for some reason very
few servers and very few clients actually implement it. Which is
silly because it's extremely easy to do.
Your email is still transmitted in the clear, of course.
--
-ed falk, [EMAIL PROTECTED] See *********************#*************#*
http://www.rahul.net/falk/whatToDo.html #**************F******!******!*!!****
and read 12 Simple Things You Can Do ******!***************************#**
to Save the Internet **#******#*********!**WW*W**WW****
------------------------------
From: [EMAIL PROTECTED] (Edward A. Falk)
Subject: Re: substring reversal
Date: 29 Jul 2000 23:28:59 GMT
In article <8ltmu2$2i8q$[EMAIL PROTECTED]>,
Edward A. Falk <[EMAIL PROTECTED]> wrote:
>
>During WWII, a "double transposition" cipher was actually in use,
>IIRC. Take your message, strip out punctuation, and write it
>out in fixed-length rows:
>
> THEDOGJ
> UMPEDOV
> ERTHEFE
> NCEAAAA <= (note the padding)
Aieeee! WTF was I thinking? Padding to a fixed length is very, very
bad. I'm several hundred miles away from my copy of Kahn, but unless
you need the padding to make the rows & columns come out even (I doubt
it), don't do this.
Good thing I don't do this for a living.
--
-ed falk, [EMAIL PROTECTED] See *********************#*************#*
http://www.rahul.net/falk/whatToDo.html #**************F******!******!*!!****
and read 12 Simple Things You Can Do ******!***************************#**
to Save the Internet **#******#*********!**WW*W**WW****
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Enigma with Transpostion (German Mechanisation)
Date: Sat, 29 Jul 2000 23:44:15 GMT
On Sat, 29 Jul 2000 18:02:28 +0200, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote, in part:
>
>
>John Savard wrote:
>
>> Given the idea of a message as an array of symbols, the Enigma
>> plugboard changed the values of symbols in the array, it did not move
>> them to other positions in the array. Of course, the values in an
>> S-box can themselves be thought of as subject to a transposition
>> (i.e., the Ohaver method) - but their action on the message is still
>> one of substitution.
>
>Maybe I misunderstood. But I don't yet see how a substitution
>(in general) can be interpreted as a transposition. (Could you
>please explain or give a pointer to the Ohaver method?)
To make a cipher alphabet from a keyword which contains some repeated
letters, the Ohaver method does this:
s u b s t i t u t i o n
S U B T I O N
A C D E F G H J K L M P
Q R V W X Y Z
BDV IGY L NP OM SAQ EW TFX HZ K UCR J
so the substitution
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
===================================================
B D V I G Y L N P O M S A Q E W T F X H Z K U C R J
was produced by a process similar to columnar transposition.
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: Sun, 30 Jul 2000 04:50:49 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Proving continued possession of a file
=====BEGIN PGP SIGNED MESSAGE=====
[EMAIL PROTECTED] wrote:
> In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] wrote:
> > Alice can store M mod (p-1)(q-1) instead of M (unless (p-1)(q-1) > M,
> > but that means the data needed to verify possession of a file is at
> > least as large as the file itself).
>
> Alice doesn't have to store M or anything else.
Sorry, I meant Bob, but that's wrong, as you point out.
- --
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
iQEVAwUBOYOl/jkCAxeYt5gVAQESWgf/eveeU8PWY68Sd5M4qeQW4Lc77aRZdy7L
A45636Wjj1Q6H7YL4K2bBaEuGw20wUzPLFWRHhAo5+JXGI/vPEU45+N3sHpKMiq4
wu3Jqy7HgL4qMb32c6SR8W0T1o7zK7bsR5789o9LhkPEmZhqny4oy0pkoCYmwhzD
n4BKhU2XUDpEsZqg48487mV0gHifCwvB9Er+84pEOpFb+CWCvtDnBUs1hC/m9gq2
c0h5QbqqzuSolYVTKGW0QPp/8IRV4deHeigVs/C6GjAH6t3XeluXdgaGmJh5WC9w
yYQb7p3s0LF58VBR1/ek32RGJFZ6DufgsigMbNjJbvb+EWR6Bjo0Gg==
=IEJj
=====END PGP SIGNATURE=====
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: How is the security of Outlook Express encryption ?
Date: 29 Jul 2000 21:46:35 EDT
CMan wrote:
>I ran one of those sniffer programs on my PC (Windows 98). I was surprised
>to see my very private user name and password go out of my machine IN THE
>CLEAR during every request for mail from my ISP. This of course is a
>problem with the protocol, not with Outlook. Makes you kind of wonder what
>else is going out on that network connection.
Are you worried about someone sniffing your phone line, or are you
using some other connection method?
------------------------------
From: Samuel Paik <[EMAIL PROTECTED]>
Subject: Re: Bluetooth security source code
Date: Sun, 30 Jul 2000 01:51:50 GMT
Tome' wrote:
> I'm looking for source code of Bluetooth. In particular i'm
> interested in encryption algorithm and authentication algorithm.
> Can someone help me ?
The Bluetooth cryptography algorithm looks to be documented in the
Bluetooth specification suffiently to implement without reference
to other sources. Is there a specific point you are puzzling about?
Sam paik
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: The Purple Cipher (World War II)
Date: Sun, 30 Jul 2000 04:34:05 GMT
On Thu, 27 Jul 2000 18:51:18 GMT, [EMAIL PROTECTED] (JimD)
wrote, in part:
>The Purple was a different animal altogether. Unless I'm mistaken
>it was enciphered code and not a cipher.
You are mistaken; or are you? I think you are thinking of JN-25, which
was a code, with additive tables. But PURPLE messages did also include
some codewords from a small code of common phrases; but their primary
encryption was by a machine that behaved somewhat like a rotor
machine.
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] (Edward A. Falk)
Crossposted-To: alt.security.pgp
Subject: Re: Re: PGP US Versions Broken,no good??
Date: 30 Jul 2000 05:38:19 GMT
>
>This is all kind of beside the point though, since 5.0i is kind of
>obsolete. Where is the best, most current version of pgp for Unix
>nowadays?
To answer my own question, I put the question to Dave Del Toro at a
talk today, and he gave his blessing to GnuPG 1.01 and 6.5i available
at www.pgpi.org
--
-ed falk, [EMAIL PROTECTED] See *********************#*************#*
http://www.rahul.net/falk/whatToDo.html #**************F******!******!*!!****
and read 12 Simple Things You Can Do ******!***************************#**
to Save the Internet **#******#*********!**WW*W**WW****
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: counter as IV?
Date: Sun, 30 Jul 2000 03:25:40 -0400
Simon Johnson wrote:
> Yes its desirable, and therefore usally the case, to spen a long
> time setting up the sub-keys for the rounds. The reason being is
> it makes Brute-Force attacks more computationally difficult, if
> the key sheduling algorithm uses wierd and slow functions.
I have to disagree with that. If a brute-force attack is feasible
at all, trying to protect against it by such means is futile.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: A naive question
Date: Sun, 30 Jul 2000 03:30:59 -0400
Simon Johnson wrote:
> I would have thought that doing two transpositions would be
> equivelent to one transposition,
No, they're in "orthogonal directions".
------------------------------
From: [EMAIL PROTECTED] (Mack)
Subject: Re: How secure is Pegwit?
Date: 30 Jul 2000 07:40:16 GMT
>
>That's what poetry is for. Easily memorizable, provides arbitrary long
>randomized passwords. Two examples.
>
> 1 Stonecutters, cut it on stone,
> Woodpeckers, peck it on wood -
> There is nothing for a woman as bad,
> As a man who thinks he is good.
>
>Password = SciosWpiowTinfawabAamwthig (How many bits of randomness?)
26 letters = about 122 bits if we ignore the capitals
Caps adds another 26 bits at most.
This assumes the letters are really random.
Since they aren't it could probably be reduced some
but not by any obvious method.
Using letter frequencies would probably help.
Notice q,x,z are absent.
>
> 2 Bis unsere Hand in Ashen stiebt.
> Soll sie vom Schwert nicht lassen.
> Wir haben lang genug geliebt,
> Wir wollen endlich hassen!
>
>Password = BuHiAsSsvSnlWhlggWweh
21 letters = about 98 bits if we ignore the capitals
Caps adds another 21 bits at most.
>
>You can take the last letters of the words as well. Is there a
>dictionary
>attack already developed against "poetic passwords"?
No known dictionary anyway but I am sure that
the letter named agencies have now started developing them.
>
>Best wishes BNK
>
>
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
From: [EMAIL PROTECTED] (Mack)
Subject: Small block ciphers
Date: 30 Jul 2000 07:49:42 GMT
Has the field of building small block ciphers
been neglected? Skipjack used a 16 bit four
round cipher as an S-box. This is reported to
be part of a family of ciphers used in Type 1
crypto hardware.
Presumably Skipjack was at the low end of
this family. Although it has a very low safety
margin it is still an interesting design.
Has anyone experimented with similar designs?
Does anyone have any 'good' short block ciphers
laying around?
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
From: [EMAIL PROTECTED] (Mack)
Subject: Re: Small block ciphers
Date: 30 Jul 2000 08:07:25 GMT
>Has the field of building small block ciphers
>been neglected? Skipjack used a 16 bit four
>round cipher as an S-box. This is reported to
>be part of a family of ciphers used in Type 1
>crypto hardware.
>
>Presumably Skipjack was at the low end of
>this family. Although it has a very low safety
>margin it is still an interesting design.
>
>Has anyone experimented with similar designs?
>Does anyone have any 'good' short block ciphers
>laying around?
>
>
>
>
>Mack
>Remove njunk123 from name to reply by e-mail
>
Also the global structure that was analysed
via impossible differentials used much smaller
words.
Studying such structures would seem to benefit
future designs.
Has anyone studied various global structures
for use in cipher design?
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Randomize, RandSeed and PRNG
Reply-To: [EMAIL PROTECTED]
Date: Sun, 30 Jul 2000 08:55:56 GMT
James Pate Williams, Jr. <[EMAIL PROTECTED]> wrote:
: [EMAIL PROTECTED] (Daniel) wrote:
:>Are there other (pseudo) random number generators available for
:>Delphi?
: [...] do a web search on the "Mersenne twister", another pseudo-random
: generator with "good" statistical properties.
Mersenne Twister for Delphi is now available here:
http://www.math.keio.ac.jp/~matumoto/july00.html
...though apparently it's mainly a Delphi wrapper around some machine
code. I presume portability "isn't much of an issue" with Delphi.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Namaste.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Enigma with Transpostion (German Mechanisation)
Date: Sun, 30 Jul 2000 11:34:14 +0200
John Savard wrote:
> Mok-Kong Shen<[EMAIL PROTECTED]> wrote:
>
> >
> >Maybe I misunderstood. But I don't yet see how a substitution
> >(in general) can be interpreted as a transposition. (Could you
> >please explain or give a pointer to the Ohaver method?)
>
> To make a cipher alphabet from a keyword which contains some repeated
> letters, the Ohaver method does this:
>
> s u b s t i t u t i o n
> S U B T I O N
> A C D E F G H J K L M P
> Q R V W X Y Z
>
> BDV IGY L NP OM SAQ EW TFX HZ K UCR J
>
> so the substitution
>
> A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
> ---------------------------------------------------
> B D V I G Y L N P O M S A Q E W T F X H Z K U C R J
>
> was produced by a process similar to columnar transposition.
Thanks. I see this as a new method of permuting the alphabet with
a key. With that permuted alphabet one can do a monoalphabetic
substutition. But the method itself doesn't do substitution in the
sense of changing the characters of an arbitrarily given message in
natural language into ciphertext. In fact, any transposition doesn't
change the single letter frequencies of a message while substitution
does change frequencies in general. This establishes that substituion
can't be achieved in general through transpositions (not even at
finer granularity, i.e. at the bit level).
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Daniel)
Subject: Re: Randomize, RandSeed and PRNG
Date: Sun, 30 Jul 2000 09:22:27 GMT
On Sat, 29 Jul 2000 21:44:58 GMT, [EMAIL PROTECTED] (James Pate
Williams, Jr.) wrote:
>On Sat, 29 Jul 2000 20:54:41 GMT, [EMAIL PROTECTED] (James Pate
>Williams, Jr.) wrote:
>
>>On Sat, 29 Jul 2000 20:28:57 GMT, [EMAIL PROTECTED] (Daniel)
>>wrote:
>>
>>>Are there other (pseudo) random number generators available for
>>>Delphi?
>>
>>They probably use the linear congruence method:
>>
>>X[n+1] = a * X[n] + b (mod T)
>>
>>where X[0] is the seed. This is a method of rapidly generating
>>pseudo-random numbers. See Knuth volume 2 for more information on the
>>generation of "good" pseudo-random numbers. I have an implementation
>>of the additive pseudo-random number generator from Knuth.
>
>Here is a C++ implementation of the additive pseudo-random number
>generator. See _Seminumerical Algorithms the Art of Computer
>Programming Volume 2_ by Donald E. Knuth second edition page 27
>Algorithm A (Additive number generator).
>
Thank you for this piece of code and your explanations on this
difficult topic! It seems I need to get a good look a Knuth's books
then.
Daniel
------------------------------
From: [EMAIL PROTECTED] (Daniel)
Subject: Re: Randomize, RandSeed and PRNG
Date: Sun, 30 Jul 2000 09:28:10 GMT
On Sun, 30 Jul 2000 08:55:56 GMT, Tim Tyler <[EMAIL PROTECTED]> wrote:
>James Pate Williams, Jr. <[EMAIL PROTECTED]> wrote:
>: [EMAIL PROTECTED] (Daniel) wrote:
>
>:>Are there other (pseudo) random number generators available for
>:>Delphi?
>
>: [...] do a web search on the "Mersenne twister", another pseudo-random
>: generator with "good" statistical properties.
>
>Mersenne Twister for Delphi is now available here:
>
> http://www.math.keio.ac.jp/~matumoto/july00.html
>
>...though apparently it's mainly a Delphi wrapper around some machine
>code. I presume portability "isn't much of an issue" with Delphi.
>--
>__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
> |im |yler The Mandala Centre http://mandala.co.uk/ Namaste.
I was very pleased that Delphi is used in Japan! Thank you for this
lovely piece of information.
Daniel
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Proving continued possession of a file
Date: Sun, 30 Jul 2000 09:39:55 GMT
Mark Wooding gave an algorithm that allowed Alice to verify
that Bob had a file. He asked if anyone could make it
faster. I then gave an algorithm that would let *anyone*
(e.g. Victor) interact with Bob and verify it. It was also
slow. Then I gave an algorithm that allowed Bob to post a
short message once a day, and anyone reading it could
verify non-interactively that he had the file. That was
even slower. Andru Luvisi proposed a way to speed up
the original algorithm, but it wasn't secure.
There is a simple way to speed up all these algorithms.
They were all computationally expensive for Bob, because
he had to calculate expressions like:
a^M mod n
where M is the entire file, possibly gigabytes long. It is
possible to greatly reduce Bob's computation by partitioning
the file into blocks of, say, 1000 bits each, and
defining:
x_i = ith block of 1000 bits within the file
y_i = concatenate(i, x_i)
M = y_1 * y_2 * y_3 * ...
Now M isn't the file itself any more, but a simple function
of it. If the original algorithms are run with this new
definition of M, they will still succeed in proving that Bob
has the file. But now, exponentiation can be done in time
linear in the size of M, because:
a^M mod n = (...(((a^y_1)^y_2)^y_3 ...) mod n
With this definition of M, it is now practical to actually
use these algorithms.
LCB
In article <8ltusp$rmb$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> I've found an algorithm that lets Bob post non-interactive
> proofs that he has a certain message M. For example,
> Alice and Bob might sign a contract that required Bob to
> hold a backup file for her. He would have to prove to the
> world once a day that he still had M. The proof should be
> short and non-interactive, even if the message M is terabytes
> long. Anyone should be able to read the proof, and verify
> that Bob isn't cheating, but still has the file. The
> algorithm here is too slow, but it may be secure.
>
> Initially Alice has the file M, and generates:
>
> s = 10 (use higher numbers for more security)
> p, q = randomly chosen primes
> n = p * q
> a = M^(-s) mod (p-1)(q-1)
>
> Alice publishes a signed file containing:
>
> s, n, a
> Alice and Bob's names, and the filename for M
>
> Alice can then forget everything, including M.
> Now, each day Bob must post a short file that can be
> combined with Alice's published file to prove he still
> has M. On any given day, Bob generates:
>
> r = secure hash of the concatenation of last night's
> closing prices for the first 10 stocks
> listed alphabetically on the New York Stock
> Exchange.
>
> Bob then publishes the date and the single
> number b:
>
> b = r^(M^s) mod n
> = (...(((r^M)^M)^M)...^M) mod n
>
> If Victor wants to verify Bob's claim today, he
> first calculates r for the published date, then
> he verifies that:
>
> (b ^ a mod n) == r
>
> If they are equal, then Bob must have had a copy
> of the file M sometime between market close on the
> listed date and the present.
>
> The work that Bob must do is proportional to s.
> The work that Alice and Victor must do is very
> small, and is independent of s. If s is too
> small, then Bob will be able to cheat. s=10
> should be safe.
>
> LCB
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
>
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Small block ciphers
Date: Sun, 30 Jul 2000 12:19:27 +0200
Mack wrote:
> Has the field of building small block ciphers
> been neglected? Skipjack used a 16 bit four
> round cipher as an S-box. This is reported to
> be part of a family of ciphers used in Type 1
> crypto hardware.
I don't know for sure but I conjecture that due to the advancements
of hardware technology, it has become practical and economical
to employ larger block sizes (for hardware implementations) which
can be exploited in design to better (more efficiently) provide higher
strength. Since the opponent is also profited by better technology,
the natural tendency is having increasingly larger block sizes, see
AES. On the other hand, given modules of a certain block size,
one can use them in a way that provide higher strength, like the
case of 3DES or using sort of recursion to apply the smaller
block size algorithm (see the thread 'On higher order Feistel
schemes' of 13 May), but this cannot compete in general with
genuine designs with larger block sizes in computational efficiency
for obvious reasons.
M. K. Shen
------------------------------
** 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
******************************
