Cryptography-Digest Digest #527, Volume #13 Tue, 23 Jan 01 02:13:00 EST
Contents:
Re: Block algorithm on variable length without padding - redux ("Scott Fluhrer")
Re: cryptographic tourism in Russia (Dido Sevilla)
Re: Block algorithm on variable length without padding - redux (David Wagner)
Re: 32768-bit cryptography ("Scott Fluhrer")
Re: Some help please (Dido Sevilla)
collisions risks of applying MD5 or SHA1 to a 48-bit input ("JL")
Re: Dynamic Transposition Revisited (long) ("John A. Malley")
Re: collisions risks of applying MD5 or SHA1 to a 48-bit input (Paul Rubin)
Re: JPEG infidelity for crypto (Dido Sevilla)
Re: using AES finalists in series? (Bryan Olson)
Re: 32768-bit cryptography ("Scott Fluhrer")
Re: Dynamic Transposition Revisited (long) ("Matt Timmermans")
Re: Dynamic Transposition Revisited (long) ("Matt Timmermans")
----------------------------------------------------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Block algorithm on variable length without padding - redux
Date: Mon, 22 Jan 2001 20:42:37 -0800
N. Weicher <[EMAIL PROTECTED]> wrote in message
news:3AYa6.28351$[EMAIL PROTECTED]...
> Scott Fluhrer was kind enough to offer the following reply to my question:
>
> > That doesn't work: You don't need to know the key to get the final
partial
> > block, and *neither does the attacker*. Doing:
> > C(N) = P(N) ^ E(C(N-1))
> > would work...
>
> My question is: would the technique shown above be just as secure as the
> full "ciphertext stealing in CBC mode" outlined on pages 195/196 in
"Applied
> Cryptography"?
I don't have a copy of _AC_ in front of me, but if I recall correctly, the
above suggestion *was* what Schneier mentioned.
--
poncho
------------------------------
From: Dido Sevilla <[EMAIL PROTECTED]>
Subject: Re: cryptographic tourism in Russia
Date: Tue, 23 Jan 2001 12:55:11 +0800
stanislav shalunov wrote:
> "NSA"? GOST is "GOsudarstvennyj STandart" (State Standard), and its
> anologue in the U.S. would be ANSI, not NSA.
>
I stand corrected!
--
Rafael R. Sevilla <[EMAIL PROTECTED]> +63 (2) 4342217
ICSM-F Development Team, UP Diliman +63 (917) 4458925
OpenPGP Key ID: 0x0E8CE481
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Block algorithm on variable length without padding - redux
Date: 23 Jan 2001 05:01:24 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Matt Timmermans wrote:
>Not quite. It is effectively encoding the last partial block with a stream
>cipher, and so it's vulnerable to the bit-flipping attacks if you don't
>include a message digest.
Yes, but plain encryption in any other block cipher mode of operation
should not be assumed to provide message integrity protection, either.
So I don't think this is a problem; it's not a goal of the construction.
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: 32768-bit cryptography
Date: Mon, 22 Jan 2001 20:57:54 -0800
lemaymd <[EMAIL PROTECTED]> wrote in message
news:94i87e$d0e$[EMAIL PROTECTED]...
> Poncho,
> How does this algorithm look? Eight identical rounds are performed on
> each byte and each key value is rotated to the left one position after
each
> round.
>
> C[I] =
>
(((((((((K1[I]^P[I])+K2[I])>>>K3[I])^K2[I])+K1[I])>>>K2[I])^K3[I])+K3[I])>>>
> K1[I])
>
> K1, K2 and K3 are key derived values and the symbols use the conventions
you
> listed in your post.
This looks almost as vulnerable to my attack. This attack is based on the
following observations/assumptions:
- In transforming N consecutive bytes of plaintext into ciphertext (that is,
8*N bits), the transform can be fully described by specifying 8*N+11 bits of
internal keying data (based partially on how K1, K2, K3 are interrelated).
The revised cipher increases that to 8*N+16 bits.
- Given an arbitrary N byte plaintext section and N byte ciphertext section,
there are (at least reasonably often) approximately 2**11 values of the
above internal keying data that transforms that plaintext to that
ciphertext. This is the fishiest part of the attack, which is true if we
model the actual cipher as a random function, which it is not. With the
revised cipher, this increases to approximately 2**16 values, but this
assumption also becomes rather more plausible.
- Using dynamic programming, it is possible to explicitly derive the
approximately 2**11 internal keying values corresponding to a particular
plaintext/ciphertext pair. The revised cipher makes finding the values
somewhat more expensive, but not prohibitively so.
- Given a potential setting of internal keying data, we can check it by
using it to decrypt the corresponding range of bytes in the ciphertext of
other blocks, and seeing if it decrypts to plausible plaintext.
- We can use "crib-dragging" to find plausible plaintext/ciphertext
sequences.
That should be enough for you to draw in the dots to get the full attack.
>
> In the rotation operations the 5 lsbits of the key values are used.
Ummm, if we're talking about rotating 8 bit bytes, we need only specify 3
bits
>
> "Scott Fluhrer" <[EMAIL PROTECTED]> wrote in message
> news:94b3hv$gda$[EMAIL PROTECTED]...
> >
> > lemaymd <[EMAIL PROTECTED]> wrote in message
> > news:94aqn0$qrs$[EMAIL PROTECTED]...
> > > To all interested:
> > > Bermuda Triangle 2001 is an extremely fast, easy-to-use and secure
> > > cryptography engine. It is based on a new, 32768-bit algorithm of the
> > same
> > > name. Algorithm details can be found at my site as well as a software
> > > product that uses the algorithm, Bermuda Triangle 2001 Golden Edition.
> I
> > > also have a free cryptography engine that uses a similar (but
> > incompatible)
> > > algorithm available for download. Visit the site at:
> > > http://www.bermudatriangle.f2s.com/
> > > These software packages are written entirely in 32-bit, win32 assembly
> > > language and I can encrypt or decrypt an 8.4MB file on my Pentium(R)
166
> > in
> > > 8 seconds. Please give me your feedback!
> > This should be pretty easy to break given several encrypted blocks with
> > known plaintext (either several short messages encrypted with the same
key
> > or one long one). As I understand it, your encryption algorithm is
> > essentially:
> >
> > C[i] = ((P[i] ^ x[i]) <<< y[i]) + z[i]
> >
> > where:
> >
> > P[i] is a byte of plaintext
> > C[i] is a byte of ciphertext
> > x[i], y[i], z[i] are key dependent values, and which are repeated
every
> > 4096 bytes (and are interrelated)
> > ^ is xor, <<< is bitwise rotate, and + is addition mod 256
> >
> > Because x[i], y[i], z[i] repeat every 4096 bytes, this repetition length
> is
> > called a block.
> >
> > Here's how to rederive a good portion of the keying data: for each byte
> > within a block, locate two plaintexts that differ in that byte by one
bit.
> > If you have at least 16 plaintexts, and the plaintexts are random, you
> have
> > a good chance of having such a pair. Then, examine the corresponding
> > ciphertexts, and see the lsbit where they differ. The rotate that moves
> the
> > plaintext bit that differs to that lsbit ciphertext bit that differs
must
> be
> > correct, thus giving you the 3 lsbits of y[i]. A similar trick can work
> if
> > you don't have a single pair that differs by precisely one bit, but you
> have
> > several pairs with low-hamming weight difference.
> >
> > Once you have most of the y[i] values, you can use the
interrelationships
> to
> > derive the 3 lsbits of x[i] and z[i]. Once you have that,
reconstruction
> > the rest of the x[i], z[i] values should be straight-forward.
> >
> > --
> > poncho
> >
> >
> >
>
>
------------------------------
From: Dido Sevilla <[EMAIL PROTECTED]>
Subject: Re: Some help please
Date: Tue, 23 Jan 2001 13:01:59 +0800
Todd Luther wrote:
>
> I received this following msg, I believe it is using some simple
> monoalphabetic cipher, but I am lacking time and expertise to decrypt
> it....anyone have any ideas and if so can you please send me a reply as soon
> as possible to [EMAIL PROTECTED]
>
I have the feeling that you're getting one of those spam messages with a
block of gibberish at the end that is supposed to defeat spam filtering
software that looks for identical messages. Such gobbledygook at the
end ensures that each message is unique, nothing more, and has the
secondary purpose of causing crypto freaks like us to look for the
secret message. ;-) I've already seen more than several postings asking
about this, if I recall correctly.
--
Rafael R. Sevilla <[EMAIL PROTECTED]> +63 (2) 4342217
ICSM-F Development Team, UP Diliman +63 (917) 4458925
OpenPGP Key ID: 0x0E8CE481
------------------------------
From: "JL" <[EMAIL PROTECTED]>
Subject: collisions risks of applying MD5 or SHA1 to a 48-bit input
Date: Tue, 23 Jan 2001 05:18:08 GMT
Hi all,
I would appreciate help in the following matter: we need to differentiate
some entities based on a 48-bit value but are not very happy with storing
the
value itself. Would MD5 or SHA1 be recommended given the input is so short?
I have strong doubts (including the possibilities of calculating the hash
table offline for all 2^48 values) but thought of bouncing the idea with
better informed people. The hash would not be used for authentication
purposes (or at least not alone).
Thanks.
------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: Dynamic Transposition Revisited (long)
Date: Mon, 22 Jan 2001 21:26:33 -0800
Terry Ritter wrote:
[snip]
>
> Every possible permutation can be constructed with approximately equal
> probability provided only that we have enough state in the RNG, and in
> practice we can easily build efficient RNG's with that property.
>
> What we cannot do is construct any possible sequence of permutations.
This may be a good place to continue the cryptanalysis of the strength
of the DT cipher. A PRNG with N! states to make every permutation of
the bits in an N bit block can only generate some of the possible
sequences of permutations. There are (N!)! possible sequences of
permutations. AFAIK it's safe to say the PRNG generates N! sequences
(assuming the set of seed values is equal to the set of possible outputs
of the PRNG, both sets are of order N!.) Only N!/ (N!)! of the sequences
can ever be seen.
There *may* be exploitable relationships between successive permutations
due to this, but I can't point to any yet, just a hunch. Permutations
with certain characteristics may always follow others with other
characteristics - or perhaps permutations with certain characteristics
can never follow permutations with other characteristics. Look for
dependencies between successive permutations that hold without knowing
the exact permutations involved.
How about a permutation's cycle decomposition - its type? (If
permutation pi() has a_i cycles of length i , where 1 <= i <= N , then
the type of permutation pi() is the partition [1^a_1, 2^a_2, 3^a_3, ...
N^a_N] of N.) I'd try to find any relationships between the cycle
decompositions/types of the successive permutations produced by the PRNG
output fed through the shuffling algorithm. I'd look for a way to
predict the cycle decomposition/type of the next permutation generated
given the current permutation's cycle decomposition/type - and I'd look
for any "forbidden" transitions - is it impossible (due to the nature of
the shuffling algorithm and the PRNG) for permutations of certain cyclic
decompositions/type to be followed by permutations of some other cyclic
decomposition/type.
John A. Malley
[EMAIL PROTECTED]
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: collisions risks of applying MD5 or SHA1 to a 48-bit input
Date: 22 Jan 2001 21:30:01 -0800
"JL" <[EMAIL PROTECTED]> writes:
> I would appreciate help in the following matter: we need to
> differentiate some entities based on a 48-bit value but are not very
> happy with storing the value itself. Would MD5 or SHA1 be
> recommended given the input is so short? I have strong doubts
> (including the possibilities of calculating the hash table offline
> for all 2^48 values) but thought of bouncing the idea with better
> informed people. The hash would not be used for authentication
> purposes (or at least not alone).
Fold a secret key (80 bits or more) in with the 48-bit value, i.e.
your_secret = "RVZPB-LU8TT-44E78-CT8RW"; # 80 bits worth of random junk
stored_hash = SHA1 (48-bit-value + your_secret);
That way someone trying to attack the hash has to also know the secret.
If you want to be really fancy, use the HMAC construction (see RFC 2104)
but for most purposes the above should be adequate.
------------------------------
From: Dido Sevilla <[EMAIL PROTECTED]>
Subject: Re: JPEG infidelity for crypto
Date: Tue, 23 Jan 2001 13:36:52 +0800
wtshaw wrote:
> This is important for stegnography, to illustate technical limitations as
> means around them are addressed. I understand that there are some for
> dishonorable reasons whop wish to cloud this area of crypto so as to
> dissuade understanding of its potential. If you are unwilling to advance
> in the field, don't try to stop others.
Oh ok. Well, it would have been nice to have the purpose of your
posting a little more clear... Just learned what this is all about
after reading your reply. Forgive my ignorance.
--
Rafael R. Sevilla <[EMAIL PROTECTED]> +63 (2) 4342217
ICSM-F Development Team, UP Diliman +63 (917) 4458925
OpenPGP Key ID: 0x0E8CE481
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: using AES finalists in series?
Date: Tue, 23 Jan 2001 05:56:00 GMT
Joseph Ashwood wrote:
> [This is actually a response to several messages I simply sent
> it in response to the first message I'm replying to] I think I
> understand why AES was necessary, and a subtle prospect to make
> a future one unnecessary. Because DES was almost forcibly used
> by all the banks for public consumption, once it became so
> obviously broken, our banking infrastructure required a new
> candidate, this is of course a very good monetary reason for our
> government to fund such an effort. Also there were vast numbers
> of people who were (and still are) making use of single DES
> without the knowledge that it is out-of-date to say the least.
True enough. But before I laugh at such folly, I note that
many of my most private conversations pass over many links
with 56 fewer key bits protecting them.
> The result was that to save the security of the many, unfortunate
> sacrifices had to be temporarily made. While I expect that Mr
> Ritter will see a temporary dip in his licensing, I don't think
> it will be permanent, I hope it won't be permanent.
I have my doubts. I've been active in the group for over a
decade, and Ritter even longer. As far back as I can
recall, Ritter has been pitching his symmetric ciphers.
I've never heard him claim anyone to license or use his
ciphers. He has always had someone to blame for the lack of
a market for his work. The AES effort only changed the
focus of his condemnation.
> Others will see the same effect, I'm sure the licensing
> of IDEA will fall at least as sharply.
>
> There is a channel for out let however, and a chance at
> total redemption. It is commonly accepted that of the 3 "real"
> finalists (Twofish, Serpent, Rijndael), Rijndael has the most
> opportunity to be broken. If we as a group can capitalize on
> that, by actually breaking Rijndael, we will put some very
> large rocks in the path of acceptance of a future government
> issued standard. I'm sure that would make Mr Ritter very happy,
> it would make me very happy, and I'm sure it would make many
> others very happy.
I'd be delighted just at the shift of focus. Alas, the
current focus makes me skeptical. Sci.crypt has many
participants who have posted more ciphers than flaws they
have found in ciphers. I don't think they even realize.
> the downside is that we would have to come
> up with a cipher certification authority to help insure the
> banks. I'm sure Mr Ritter would truly enjoy being in that
> position, as would any number of us.
I sure would. But look at the talent AES brought out. We
might well assemble the greatest collection cryptanalytic
intellect the group has seen since Don Coppersmith's single
post.
--Bryan
Sent via Deja.com
http://www.deja.com/
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: 32768-bit cryptography
Date: Mon, 22 Jan 2001 22:18:00 -0800
Tom St Denis <[EMAIL PROTECTED]> wrote in message
news:94hlqv$n8q$[EMAIL PROTECTED]...
> In article <94hh9v$gpg$[EMAIL PROTECTED]>,
> "Scott Fluhrer" <[EMAIL PROTECTED]> wrote:
> >
> > I thought I outlined how to break it with considerably less known
plaintext
> > than that. In addition, I've been looking further at that (and, yes, I
> > don't have a life -- why do you ask?). It appears (at first glance)
that it
> > shouldn't be that difficult to rederive the plaintext/key from 16-20k
with a
> > ciphertext-only attack, if the plaintext was known to be (say) ASCII
> > English. If anyone wants to be bored with the details, ask.
>
> Well you could mount a linear attack with a prob of 1/8th very easily.
Just
> guess the rotation amount then you are set.
Well, yes, but using linear cryptanalysis against this cipher feels like
using a bazooka to take out a mouse. It'll work, but it lacks a bit of
elegance...
--
poncho
------------------------------
From: "Matt Timmermans" <[EMAIL PROTECTED]>
Subject: Re: Dynamic Transposition Revisited (long)
Date: Tue, 23 Jan 2001 06:54:04 GMT
"Terry Ritter" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Essentially the problem is one of ambiguity: the idea that Kahn is
> talking about a real, practical OTP, when in fact he can only be
> talking about the theoretical OTP. For example, he starts out saying:
Real practical OTP's do exist, and have been used to good effect. It's not
that hard to generate effective keying material -- you could use dice or
radioactive decay, for example. Getting the key to the intended recipient
of messages is a problem, but it's the almost the same problem you have with
regular symmetric ciphers. The only differences here are that the key is
big, and it doesn't last forever. If you can meet someone personally every
month or so and exchange CDRs, and if you have a sound card, you have can
have your regular communications protected by a perfectly viable, practical,
and provably secure OTP.
The problem newbies have understanding OTP is not in assuming that it's
provably secure (because it is), but in mistaking keyed PRNG output for an
actual random message key. The newbie cryptographer likes the idea of
provable security, but hates those nasty key requirements, so he invents a
marvelous new version of "OTP" that is practical because only a short key is
required, and the long message key can be generated from this seed. Pretty
much all of the cryptosystems that pop up here claiming to be OTP are not --
OTP is well defined, and it requires a _random_ key as long as all of the
messages your ever going to send with it, and it requires that no part of
that key ever be divulged or reused.
Oh well, newbies invent broken stuff all the time, but it certainly _is_
possible to make real one-time pads in practice, so the provable security of
OTP does not apply to theoretical systems only. And any "OTP" that
satisfies the definition of the term is, in fact, provably secure. OTP is
also the simplest provably secure cipher we can have until we prove that
P!=NP, unless you're prepared to define polynomial-time lower bounds for
known-plaintext attacks as "security".
------------------------------
From: "Matt Timmermans" <[EMAIL PROTECTED]>
Subject: Re: Dynamic Transposition Revisited (long)
Date: Tue, 23 Jan 2001 06:59:46 GMT
"John Savard" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
> However, for larger block sizes, one can indeed do better than that.
>
> One can map 37 arbitrary bits (137438953472 possibilities) to 40
> balanced bits (137846528820 possibilities) for only an 8.11% increase
> in bandwidth cost.
>
> Or one can map 158 arbitrary bits
> (365375409332725729550921208179070754913983135744 possibilities) to
> 162 balanced bits (365907784099042279561985786395502921046971688680
> possibilities), which further reduces the bandwidth cost to 2.532%.
>
> So I suppose you could say that I am quite seriously in need of
> "recalibration".
Alternatively, you could XOR the plaintext with a psuedo-random stream, and
then use Terry's simple balancing operation. The probability of wasting a
significant number of bits gets quite small as the blocks get long.
------------------------------
** 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
******************************
