Cryptography-Digest Digest #332, Volume #12 Tue, 1 Aug 00 23:13:00 EDT
Contents:
Re: counter as IV? (David A. Wagner)
Re: Skipjack and KEA test vectors (Jason Stratos Papadopoulos)
Re: counter as IV? (David A. Wagner)
brute force passtext crack software, which is the best ... (jungle)
Re: Proving continued possession of a file (David A. Wagner)
Re: Proving continued possession of a file (David A. Wagner)
Re: Proving continued possession of a file (David A. Wagner)
Re: Small block ciphers (David A. Wagner)
Re: Small block ciphers (David A. Wagner)
Re: Stream Ciphers (Benjamin Goldberg)
Re: Skipjack and KEA test vectors (Eric Smith)
Re: Proving continued possession of a file ([EMAIL PROTECTED])
Re: Sending Messages in Morse Code (Terry Ritter)
Re: Secure key-based steganography ([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: counter as IV?
Date: 1 Aug 2000 18:10:17 -0700
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
> Consider the scheme:
> secret key K established
> counter N, init 0
> for each plaintext block Bi:
> encrypt Bi using key (K XOR N) in algorithm E
> increment N
[...]
> The question I have is this: What *specific* weakness is
> introduced by using a simple counter N instead of a truly
> random IV? I.e., how does using a counter facilitate
> cryptanalysis or some other more meddlesome attack?
Some others have mentioned that it may allow related-key cryptanalysis,
and I wanted to elaborate with a specific, concrete example of how this
construction can introduce weaknesses. I won't claim the attack is
entirely practical, but it should give you pause. Please excuse the
scary-seeming notation; the idea really is very simple, but I don't know
how to express it more simply at the moment.
Let E be three-key triple-DES encryption, where each key K for E is
three DES keys K_1,K_2,K_3, and
E(K,B) = DES(K_3,DES(K_2,DES(K_1,B))).
Suppose that the sender transmits the same block B twice. In your
scheme, B will be encrypted first with L = K XOR N to yield the first
ciphertext C = E(L, B), and then the second repetition will be
encrypted with L' = K XOR (N+j) = L XOR N XOR (N+j) to yield the
second ciphertext C' = E(L', B).
Assume that N is represented in little-endian format. Then usually
incrementing N flips just a few of its low bits, so L and L' will differ
only in their third component, i.e., L_1 = L'_1, L_2 = L'_2. Also,
if we assume that the counter values N are known, then the difference
D = L_3 XOR L'_3 = N XOR (N+j) will be also known to the attacker.
Then we can note that
DES(L_3 XOR D, DES^{-1}(L_3,C) ) = C'. (*)
Since C, C', and D are known, we can search for L_3 using exhaustive
keysearch, with complexity 2^57. This reveals L_3, and since N is presumed
to be known, the attacker learns 56 bits of the master key K, namely, K_3.
Once K_3 is known, we can reduce the system to just a double-DES system,
and there are known attacks to break double-DES with complexity somewhere
between 2^56 to 2^72 (depending on the cost of memory). So the whole
system can be cracked with roughly this level of complexity, at least
under conditions favorable to the cryptanalyst as outlined above.
The above attack is basically a straightforward application of ideas
found in
John Kelsey, Bruce Schneier, and David Wagner,
``Key-schedule cryptanalysis of IDEA, G-DES, GOST, SAFER, and triple-DES.''
CRYPTO'96. http://www.cs.berkeley.edu/~daw/papers/keysched-crypto96.ps
This shows that, at least in the case of three-key triple-DES, your
construction substantially reduces the complexity of attack. We can
expect that other ciphers vulnerable to related-key cryptanalysis (and
there are a large number of them) may also be problematic for this
construction. So, as a general mode of operation, your proposal seems
to have some undesirable properties.
------------------------------
From: Jason Stratos Papadopoulos <[EMAIL PROTECTED]>
Subject: Re: Skipjack and KEA test vectors
Date: 2 Aug 2000 01:14:34 GMT
Mark Wooding <[EMAIL PROTECTED]> wrote:
: My implementation agrees completely with Lewis' test vectors. Together
: with the official Skipjack test vector, I think they test something like
: all but 16 F-table entries.
When Skipjack was first released I posted the following from a C
implementation I cobbled together:
Plaintext Key Ciphertext
1ddf39abf5cd711e f8da02647722f7103adf c92d22324c6b31ae
dd6c6cce8f83e69e 82760ac137948821eee4 e32877c1d9527fff
beaacf177fa41a11 843c1687d3cdca5fc5c3 4745783f75b8861a
c4c09f216c1bc60a ae870cd7ff33a995f7e5 5c101636b8a57a72
d3f814b000245856 5ccbd913ea8b73bd6391 b4fc0f8e54728f91
356ec7d93832329c f65e74cd599c68a40cc7 93b750608f5701f8
209ecf1c537ad56c aa106e46d7087c4e93dc d823d45510099e61
892eea9d64e17d66 a93f9789a20c3cc34fea 0959e231b275d95f
991390fd760fc91b 88b163cbd61616888899 e7700209886767ae
daebc947ddca9c9e fb6cd1ff70487561df10 e7cc49a56bd6a322
6419ddefe2cd8f2e 5edc1ac0c4e7ef5f002c e48a05cf26e242fd
322998ecbd068112 8e3090c19aa32f94496a 62c0e537b14df2c1
3aae2aee20da93cc b96e3fd46fa4263f9092 54d1e58a6b624d71
14311112ca11f727 9e6635baee28c5bce2bc 5d0f235a9d221ce0
300e4313e7ad6796 04127ce16dc1b1726a66 8e5b03522e68cbeb
09cd1c1accbe7797 f0b89d75e979ccc9b172 572c9b4025a9134b
31b30ca354af3cd8 f9bfc78798cbf1bcd4b5 8c959c904789fbda
08c59b0db99ec267 f43a51b4273bde27d2b0 b7d7f5fa342988fb
9784b1e3e7e60e60 cd51f0a75aa73c48edd2 763aa8ee109397b3
f65216373d4b43c7 b3319a3f6622aa726bb3 0325600337b8ad3c
cba4c1215d5d36ce 493254c9596e993f5f9c 68e1c551c59108c0
82294851288e75cb 76150c2c3ced1c7ca021 7eb6325d82a2096c
c3a7b7e4a52e407b 7140d6c5486305872df6 2483f385a42ee3c6
1bfde32ab559e13a 3c2c3901f0ee9a3b2b0e d6fa9db8685fd88a
d205f7486c782838 606a8b4bdfaae8a0ba51 0330489170b85293
d96ff1f7c7fc60e0 7847a47a0fe79ab770ce 1f9b3301c9b2708c
241d4bde19a75f8f 73b9ab0c36c99e91a891 2b86c57ffe168895
7be1b8d58321c619 a37f2ad5a85e170741f5 5af7ceb3eed9dca1
c9214ea01ec14948 f7b0c2a8170e3c4e48b3 1b587736e116c04b
e2a3091feb581588 a1fc67e44eacacf4a902 f3ecf0f1789a3923
3cb466d301b60854 f14430affc5fe82a9ae9 e8d114c20ffa1c79
b0684f8a5e63d935 fd26df50486a4cd96d9b 222903994d64fe3a
ba1f37e88edec55f a6d46d46ca287e1a332a 91f2baad6fa0de55
e9fed8501b7a6579 83c3f1cb8d06efc6196b 83f9f08f89a854ee
eb5ca8b3fa1fcdbb 0edfa44c7d4a4ef0725e 2b1b6670a6be0324
b8b525c6382af277 b8edcf167d99a711ccee 211a695da473766f
9162e781ff683853 4f639e0d5a5d2ad7e9a4 eb2976370d22ef22
c9f23a20a39ded11 37e006256a4ae6d320c4 dba4c0ef0ea098c0
5a6f12f32f7eefdf e41d0bd25f931ba1d85c 923daee8000709f9
cad5414c1c64f194 fdf65bbc5fe600f3cd68 d5771e78b6f1fe1e
063a58a20b45378f 1c269af2ff166acb27ef 634f7a3861af97a1
08fbf42b4313347b 1179f64acb6122ccf649 3a803a4bd0e8c3e6
6d4ed0e9930532d1 078c87265eb8da323e90 f4fa372e7e1441a1
40b699812345661d 2fff35f8eb774c843bb0 63a9197f7b75f53f
22ed54626a51e505 09f77346a4393ce99856 e91a050a7481b3dd
0c489b66e2da531b 5b878e0b22a705acf8fb 6e9370a91b994878
c64b10f8b191bc2c 9d72c1ab2092c1b10877 5bdecded96d656c9
91fdf7236f85bdd6 72865f289725e1b55502 1a5680e51736026f
40009f8a465a9feb 06e3c0e541f4aae6fe93 0e7aace421bc79d8
543208b05bfa3858 2ea09f1cc89e064f09bc a95d87fad12c3593
The F table matches an initial implementation in Ada somebody posted at
that time, and I got independent verification from someone else's
implementation that the results match. The NIST test vector alone uses
about half the F table iirc, and the above will use all of it.
Hope this helps,
jasonp
PS: No, I haven't tried to reproduce the KEA vector.
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: counter as IV?
Date: 1 Aug 2000 18:16:01 -0700
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
> Consider the scheme:
> secret key K established
> counter N, init 0
> for each plaintext block Bi:
> encrypt Bi using key (K XOR N) in algorithm E
> increment N
By the way, here's another way to view the problem with this construction.
It is hard to identify the set of requirements on E needed for the
resulting scheme to be secure. In other words, there is no proof of
security that this yields a secure mode of operation if E is a secure
cipher (say, indistinguishable from a random permutation). In contrast,
standard modes such as CBC mode _do_ possess such generic proofs of
security, and thus appear like a very good starting point.
Note that your proposal _can_ be modified to allow a proof of security.
Introduce a secure pseudo-random function F, and choose the secret key K
from the keyspace of F. Then,
set N := 0
for each plaintext block Bi:
let L_N := F(K, N)
encrypt Bi using key L_N in algorithm E
increment N
It is straightforward to prove this secure (so long as N never repeats).
------------------------------
From: jungle <[EMAIL PROTECTED]>
Subject: brute force passtext crack software, which is the best ...
Date: Tue, 01 Aug 2000 21:21:51 -0400
BRUTE FORCE PASSTEXT crack software, which is the best ?
=========================================================
looking for reference to BRUTE FORCE PASSTEXT crack software ...
to test passtext quality ...
to be :
- very flexible in the options to build words relations & word catenation
OR
- providing substantial list of default options for word list AUTO modification
- multiple words lists, when possible
- will search against passtext / vector / list / matrix /
- free to evaluate
- run in DOS / win95
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: Proving continued possession of a file
Date: 1 Aug 2000 18:22:57 -0700
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.
What's wrong with applying the standard heuristic to turn any interactive
proof into a non-interactive one? Let D be the date, and H be a hash
function (with sufficiently large output length) that can be modeled as
a random oracle. Take any interactive protocol for proving continued
possession of a file. Then we run the interactive protocol, except that
the challenger should use H(D) as his random bits instead of generating
truly random bits. If we publish D and the trace of this simulated
protocol run, doesn't this give us a nice concise non-interactive proof
as desired?
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: Proving continued possession of a file
Date: 1 Aug 2000 18:32:50 -0700
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.
What's wrong with applying the standard heuristic to turn any interactive
proof into a non-interactive one? Let D be the date, and H be a hash
function (with sufficiently large output length) that can be modeled as
a random oracle. Take any interactive protocol for proving continued
possession of a file. Then we run the interactive protocol, except that
the challenger should use H(D) as his random bits instead of generating
truly random bits. If we publish D and the trace of this simulated
protocol run, doesn't this give us a nice concise non-interactive proof
as desired?
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: Proving continued possession of a file
Date: 1 Aug 2000 18:39:04 -0700
In article <8m0t5b$pec$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
> Mark Wooding gave an algorithm that allowed Alice to verify
> that Bob had a file. He asked if anyone could make it
> faster. [...]
>
> 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.
Uhh... but Mark Wooding's exponentiation a^message mod n can
already be done in time linear in the size of the message.
And y_1 * y_2 * ... is no smaller than the message, so your
scheme is likely to be slower than Mark Wooding's scheme.
And, I'm not entirely convinced your scheme is secure. Is the
map (x_1,x_2,..,x_n) |--> y_1 * y_2 * ... * y_n truly injective?
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: Small block ciphers
Date: 1 Aug 2000 18:43:23 -0700
Mack <[EMAIL PROTECTED]> wrote:
> Has the field of building small block ciphers
> been neglected?
No. There is a _ton_ of cryptographic literature on S-box design.
(I take it you are intending these things for use as internal components
of a cipher, in which case they are more properly called S-boxes.
The word "block cipher" is probably best reserved for the externally
visible functionality, not the internal invisible components.)
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: Small block ciphers
Date: 1 Aug 2000 18:46:26 -0700
Mack <[EMAIL PROTECTED]> wrote:
> Studying such structures would seem to benefit
> future designs.
If you were planning to study S-box design, the first question to ask
yourself is: What are the relevant metrics?
Note that this question will not have a universal answer; it will depend
on how you want to use the S-box, and often on the specific cipher design
you will be using it in. Blindly using S-boxes designed for use in one
algorithm elsewhere may lead to bad results.
In other words, there is no "a priori" correct set of metrics to choose.
You must first study how you are going to use the S-boxes, identify a set
of metrics, and justify them in the setting of your application. Then,
you can talk about how to build S-boxes that optimize those metrics.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Stream Ciphers
Date: Wed, 02 Aug 2000 01:52:53 GMT
John Myre wrote:
>
> Benjamin Goldberg wrote:
> <snip>
> > The *shortest* cycle length is 2**40 32-bit values [that is a 2**62
> > bit cycle]
> <snip>
>
> Would you like to correct this arithmetic?
>
> (Hint: 32 = 2^5, not 2^32)
> JM
Oops. The shortest cycle is 2**45 bits. My mistake.
------------------------------
From: Eric Smith <[EMAIL PROTECTED]>
Subject: Re: Skipjack and KEA test vectors
Date: 01 Aug 2000 18:59:43 -0700
Jason Stratos Papadopoulos <[EMAIL PROTECTED]> writes
about SKIPJACK:
> The NIST test vector alone uses
> about half the F table iirc, and the above will use all of it.
I instrumented my implementation, and found that the NIST test vector
uses 104 of the 256 entries in the F table. It seems inexcusable to
me that an official specification for an encryption algorithm not
be accompanied by at least enough test vectors to cover all of the
table values. Sigh.
I verified that my implmentation passes the vectors you posted on
27-Jun-1998.
My PIC implementation is available at:
http://www.brouhaha.com/~eric/crypto/
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Proving continued possession of a file
Date: Wed, 02 Aug 2000 02:03:03 GMT
In article <[EMAIL PROTECTED]>,
Andru Luvisi <[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] writes:
> [snip]
> > Bob then publishes the date and the single
> > number b:
> >
> > b = r^(M^s) mod n
> > = (...(((r^M)^M)^M)...^M) mod n
> [snip]
>
> How does Bob compute this number so as to minimize ram usage and work?
If M is stored on a hard drive, then the obvious
binary algorithm for exponentiation ("square and
multiply") would use less than a kilobyte of RAM,
no matter how big M and s were. There may be
some clever way to reduce RAM further, but
minimizing RAM doesn't seem like a big issue.
The algorithm is very slow. The point of that
post wasn't to propose a faster algorithm, but to
propose an algorithm that allowed a non-interactive
proof, and allowed anyone to verify it, not just
Alice. I think the algorithm does that securely.
I suggested s=10, but didn't say much about it.
The idea is that if M is small, then Bob can
factor (M*(M^-1)-1), which is a multiple of (p-1)*(q-1).
That would let him find p and q. So, if M is small,
Alice can choose an s>1, which means Bob will have to
factor a number with s times as many bits if he wants
to cheat. Bob will also have to do s times as much
work each day. If M is very large already, then there's
no need to use s, and Alice can just choose s=1.
In a different post, I talked about redefining M as
M=(y_1*y_2*y_3..) as a way to speed things up. As I
said yesterday, that's wrong. It doesn't make things
faster by itself. But it may be a useful component
in an algorithm that would be faster. I have some
ideas along those lines, and if I find something, I'll
post it.
LCB
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Crossposted-To: sci.math
Subject: Re: Sending Messages in Morse Code
Date: Wed, 02 Aug 2000 02:42:05 GMT
On Tue, 01 Aug 2000 22:18:42 +0200, in
<[EMAIL PROTECTED]>, in sci.crypt Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>[...]
>I read somewhere that the Morse code was designed to be
>optimal for transforming normal English sentences.)
Just maybe that was true of one of the American Morse codes used on
telegraph circuits for over a century (I have a key-and-sounder
"learner set" with an American Morse table dated 1960), but what we
normally think of as "Morse code" is International Morse, as
standardized in Europe. It is good but not ideal for English.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Secure key-based steganography
Date: Wed, 02 Aug 2000 02:46:15 GMT
In article <[EMAIL PROTECTED]>,
Steve Weis <[EMAIL PROTECTED]> wrote:
> Toby Sharp wrote:
> > At each visited pixel, the least significant bit of image data is
replaced
> > by the next covert message bit until all data bits have been
encoded. The
>
> Alice and Bob would have to generate an original image each
> transmission. If they use the same image over and over, Eve will
notice
> the slight changes in the image. If they choose some image which is
> publicly available, Eve will be able to compare the original with
their
> transmission. (Assuming Eve is a powerful adversary and has the
> resources to find the original image). There is also the question of
> traffic analysis. It will look suspicious if Alice and Bob suddenly
> start sending each other images and haven't had a history of doing it
in
> the past.
>
I've thought about this problem for a little while now, and one possible
solution I've come up with I call "newscasting". It works like
this:
Alice should use a picture that alot of people would be interested in
downloading (oh... <scratching head>... say maybe a porn picture) and
hide her message in it ("original" porn pictures are easy to make and
still create a high demand, infact there is are quite a few "amateur"
newsgroups devoted to just such "originals"). Then she could post it to
any number of binary newsgroups, where thousands or millions of people
would download it (if this turns her on is beyond the scope of this
posting). Bob could be downloading all the pictures on a given
newsgroup and look inside them all or he and Alice could agree on hiding
information in postings that meet certain criterion. For example,
filenames that start with 'xx' or have the word "REpost in the Subject
line, just to save on bandwidth and processor time.
This newsgroup and header criterion (and possibly a passphrase) would
constitute a "channel" of communication. I think traffic analysis would
prove difficult because of the nature of NNTP services--thousands of
pictures get posted to many of these groups daily, they are distributed
by thousands of different newsservers and delivered to millions of
different people around the world.
There are steganographic programs out there to hide information in
various picture and sound files as well as in executables. Huge
delivery potential.
What do you guys think?
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
******************************
