Cryptography-Digest Digest #334, Volume #14 Fri, 11 May 01 10:13:00 EDT
Contents:
Re: Best encrypting algoritme (Mok-Kong Shen)
Re: Information hiding in digital TV some thoughts and experiments. (Mok-Kong Shen)
Re: Crypto web-page (Mark Wooding)
Re: Horst Feistel ("Tom St Denis")
Re: Crypto web-page ("Tom St Denis")
Re: Security with provable strength. (Mark Wooding)
Re: A simple encryption algorithm based on OTP (Keill Randor)
Re: A simple encryption algorithm based on OTP ("Tom St Denis")
Re: Security with provable strength. ("Tom St Denis")
Re: Cryptanalysis Question: Determing The Algorithm? (Bo D�mstedt)
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Best encrypting algoritme
Date: Fri, 11 May 2001 15:10:01 +0200
wtshaw wrote:
>
[snip]
> As I have said before, I don't see the great need for chaining modes. I
> sometimes refer to ciphers as examples that are neither customary stream
> nor customary block ciphers.
I believe that an optimal combination of stream and block
techniques is the best. (This belief underlies one of my
humble designs.) One employs a PRNG. The operations done
in a block render the prediction of the pseudo-random source
difficult. The block operations may be also dynamically
influenced by the processing of previous rounds/blocks.
It is also possible to consider the entire message as
a single block. Thus a strict distinction of stream and
block processing is only a conceptual aid in my humble
view and is not a necessity.
> In short, everytime you encrypt the same thing, the ciphertext should
> substantially vary, no IV's, not reference to adjacent blocks. To get
> enough polymorphism, the length of the encrypted block will probably be
> longer than the plaintext considering character set size and/or length of
> the block in characters.
There are many different posssiblities to dynamically
effect 'variability' of processing of individual blocks.
Use of a pseudo-random source may be considered in this
connection. I suppose in the last sentence you are
referring to use of homophones, including introduction of
random dummies.
[snip]
> I don't see a way to grossly improve algorithms that have painted
> themselves in to the looking for any crutch mode help they can find. It
> seems that inadequate consideration took place somewhere upstream, but all
> the right questions were obviously not being asked. Surely there are many
> ways to add strength as I suggest.
It is better to have larger blocks (the extreme is the
whole message). But one has somehow decided to use block
encryption and has chosen a small block size (e.g. for
hardware reasons). In order to get nevertheless a bit the
benefits of large block processing, one employs a (particular)
technique, which is the chaining. So chaining is a compromise,
or an afterthought, if you like. It may be mentioned that
Scott has for years advocated whole file processing in the
group (though personally I am not fond of the specific
methods he uses).
> Better block ciphers have some sort of obvious key changes going on that
> allows for increased variability; best is from an input of randomness.
> The problem of reestablishing a random sequence at both ends can be
> removed if the encryptive algorithm stores the path back as part of the
> cipher text. Therefore, original random generation need not be
> duplicated.
I agree on the benefit of having variability (see above).
I don't understand what you mean by 'stores the path back as
part of the ciphertext'? (Is that utilization of previously
sent messages?)
[snip]
> Making algorithms overly complicated merely means that the program is apt
> facilitate programming mistakes, allow hanky panky room, and hide bad
> logic judgments. It is best to keep the service algorithm as transparent
> as possible. While layer upon layer of primatives can be added, each
> adding some keyspace, this wedding cake approach is apt to lead to a
> troubling group marriage between resultant algorithms, implementers, and
> users. Yes, greater strength does mean more keyspaces, but while many
> layers is an alternative approch, it does not appear to be the best by
> keeping the encryptive algorithm rather straight forward and easy to
> understand and use.
Commonly, a good block cipher has a few simple and clearly
defined layers in each round. I suppose you are not objecting
to using a number of rounds or to using multiple encryptions
with different algorithms (eventually dynamically changing
the mix).
>
> Making each block stronger requires a great increase in key size. I have
> done what looks wasteful in using huge keyspaces, but it need not be
> frightful. With lots of room to play, the means of generation to fill
> this keyspace becomes a bigger study that the base encryptive algorithm
> itself. Indeed effective keysize can be from almost nothing to the
> equivalent of tens of thousand of bits. While most want to narrowly
> define keys narrowly, I don't. After all, in the ideal algorithm the
> strength resides entirely in the keys; to get great strength, you need a
> keyspace that is frightful for an attacker to contemplate. Keeping a
> keyspace small can mean that you are running away from strength too hot to
> touch for some non-scientific reason.
I suppose that two ways are available: use a larger key
in the algorithm, or vary the key for different blocks
in some manner. It seems that there is the popular opinion
that key materials are fairly costly. However, the cost
issue surely depends on the concrete economical factors of
one's applications. One can certainly provide for the use
of keys of widely different sizes for different classes
of messages.
M. K. Shen
===========================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Information hiding in digital TV some thoughts and experiments.
Date: Fri, 11 May 2001 15:10:12 +0200
Jan Panteltje wrote:
>
[snip]
> The Internet for example can be cut by law enforcement on the local ISP's,
> in a country in a state of war, but to find satellite dishes and remove these,
> would be a whole different matter.
> Anyways these were just some thoughts after some initial experiments here...
The information in your article is valuable. Information
hiding is a very essential issue for further research.
(For encryption, the state of the art is already fairly
good, I suppose.) I think that with the development of
techniques for mobile communications and the expansion
of the total volume of information being transmitted over
diverse channels a stage will ultimately be reached
where an effective central surveilance or 'control' of
communications by a mighty institution would no longer
be feasible, if a sufficiently large portion of the
messages are encrpyted and hidden.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Crypto web-page
Date: 11 May 2001 13:14:54 GMT
Sam Simpson <[EMAIL PROTECTED]> wrote:
> I think the argument has been made before that (for example...) both
> RSA and Elgamal signatures have many gotchas that one needs to be
> aware of when coding the algorithm.
Oh, yes, indeed. I wasn't thinking about ElGamal signatures at all in
my article -- only ElGamal encryption (m |-> (g^\beta, m g^{\alpha\beta})).
And I hope that I didn't understate the various traps when actually
implementing any known public-key system.
> The difference appears to be that RSA has standard definitions for
> signatures (ANSI, the various PKCS etc) that avoid all known problems,
PKCS#1 padding worries me greatly. The padding method for encryption
has already been attacked, and I don't hold up a great deal of hope for
the signature padding stuff. PSS is the way forward, evil patents or
no.
> whereas traditional Elgamal signatures have no such standard and
> instead rely upon each implementor reading huge swathes of literature
> to get the implementation correct and avoiding the many pitfalls.
Indeed. I thoroughly recommend against using ElGamal in any real system
-- either for signatures or encryption. The former is inefficient and
difficult, and done much better by DSA; the latter offers no advantage
over plain Diffie-Hellman.
I think that my point was that all public-key systems have their various
weirdnesses and pitfalls: RSA, Diffie-Hellman, DSA, elliptic-curve
systems, err... knapsacks ;-). I was attempting to dispute that RSA was
actually much simpler than any of the others. This stuff is difficult,
and pretending it isn't doesn't do anyone any favours.
> (PS: We're still using Catacomb in the development of Scramdisk for
> Linux - cheers again!)
Oh, good-oh. ;-) I'm still adding ciphers. I think that, since the last
release, I've added DESX, SAFER-K and SAFER-SK, MARS, Noekeon and
Rijndael with 192- and 256-bit blocks. I'm also working on a Perl
interface (I've a CipherSaber implementation and half of a quadratic
sieve implemented in Perl), and I've a skeleton into which elliptic
curve crypto can be slotted when I've finally understood Dr Mike's book
-- I'm running short of patience and persistence, and haven't yet
discovered the truth.
There's a bug in the current release, by the way. The function
mprand_range ought to return a random number in the interval [0, n), but
actually returns one in the interval [0, \lceil n/2 \rceil) because of a
stupid error. This one has security implications for DSA, for example,
just to bring us back to what we were actually talking about.
-- [mdw]
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Horst Feistel
Date: Fri, 11 May 2001 13:41:35 GMT
"Jim Reeds" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> In article <[EMAIL PROTECTED]>, Paul Rubin
<[EMAIL PROTECTED]> writes:
> |>
> |> FYE-stell. But it's a German name, not American.
>
> Most Americans pronounce it with the stress on the second
> syllable (fai-STELL), even though in German it's correct to put
> the stress on the first syllable, as Paul indicates. I don't
> know which syllable HF himself stressed.
Who knows. I pronounce it like "F-hi-still". (two syllables) I used to
pronounce ElGamal "ElGamma" hehehe...
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Crypto web-page
Date: Fri, 11 May 2001 13:45:40 GMT
"Mark Wooding" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Sam Simpson <[EMAIL PROTECTED]> wrote:
>
> > I think the argument has been made before that (for example...) both
> > RSA and Elgamal signatures have many gotchas that one needs to be
> > aware of when coding the algorithm.
>
> Oh, yes, indeed. I wasn't thinking about ElGamal signatures at all in
> my article -- only ElGamal encryption (m |-> (g^\beta, m
g^{\alpha\beta})).
> And I hope that I didn't understate the various traps when actually
> implementing any known public-key system.
>
> > The difference appears to be that RSA has standard definitions for
> > signatures (ANSI, the various PKCS etc) that avoid all known problems,
>
> PKCS#1 padding worries me greatly. The padding method for encryption
> has already been attacked, and I don't hold up a great deal of hope for
> the signature padding stuff. PSS is the way forward, evil patents or
> no.
>
> > whereas traditional Elgamal signatures have no such standard and
> > instead rely upon each implementor reading huge swathes of literature
> > to get the implementation correct and avoiding the many pitfalls.
>
> Indeed. I thoroughly recommend against using ElGamal in any real system
> -- either for signatures or encryption. The former is inefficient and
> difficult, and done much better by DSA; the latter offers no advantage
> over plain Diffie-Hellman.
>
> I think that my point was that all public-key systems have their various
> weirdnesses and pitfalls: RSA, Diffie-Hellman, DSA, elliptic-curve
> systems, err... knapsacks ;-). I was attempting to dispute that RSA was
> actually much simpler than any of the others. This stuff is difficult,
> and pretending it isn't doesn't do anyone any favours.
>
> > (PS: We're still using Catacomb in the development of Scramdisk for
> > Linux - cheers again!)
>
> Oh, good-oh. ;-) I'm still adding ciphers. I think that, since the last
> release, I've added DESX, SAFER-K and SAFER-SK, MARS, Noekeon and
> Rijndael with 192- and 256-bit blocks. I'm also working on a Perl
> interface (I've a CipherSaber implementation and half of a quadratic
> sieve implemented in Perl), and I've a skeleton into which elliptic
> curve crypto can be slotted when I've finally understood Dr Mike's book
> -- I'm running short of patience and persistence, and haven't yet
> discovered the truth.
>
> There's a bug in the current release, by the way. The function
> mprand_range ought to return a random number in the interval [0, n), but
> actually returns one in the interval [0, \lceil n/2 \rceil) because of a
> stupid error. This one has security implications for DSA, for example,
> just to bring us back to what we were actually talking about.
There are ways around this. For example you can share encrypted messages
via DH without having to use ElGamal.
In PeekBoo2 I did this
1. Each user picks their own x, and publishes g^x mod p
2. To send a message to user y you compute g^xy mod p, hash that value and
call it H
3. Each time you want to send a message you pick a random IV and append it
to H, you hash IV+H and that's your secret key. You then publish IV along
with the ciphertext.
The benefit is that each message gets it's own key and doesn't require big
math to send each message.
Tom
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Security with provable strength.
Date: 11 May 2001 13:47:11 GMT
Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
> Paul Rubin wrote:
> >
> > It was attributed in AC2 to Udi(sp?) Maurer, but it's completely
> > insecure and there has to be some kind of mistake involved.
> > Think linear algebra.
>
> Not *entirely* linear. Here it is written in psuedocode, with N=128
>
> These arrays are of bits:
> K[1..N] = the secret key
> R[1..N][1..M] = the public random strings.
> P[1..M] = the plaintext
> C[1..M] = the ciphertext
>
> for( i = 1 .. M ) {
> x = P[i];
> for( j = 1 .. N )
> x ^= K[j] & R[j][i];
> C[i] = x;
> }
>
> The step with the & is *non*linear.
No, it's matrix multiplication over F_2.
Let K be a N-entry column vector over F_2, known to Alice and Bob.
Alice wants to sent a message P, expressed as an M-entry column vector,
also over F_2. She invents a random M x N matrix R over F_2, and sends
C = P + R K
This is the system you've proposed.
Let's say we want to find K. Collect N bits of plaintext and ciphertext
(and random strings R), and stack them all up in a column. You end up
with a square R matrix, which you hope is invertable, and compute
K = R^{-1} (C + P)
Trivial.
-- [mdw]
------------------------------
From: Keill Randor <[EMAIL PROTECTED]>
Subject: Re: A simple encryption algorithm based on OTP
Date: Fri, 11 May 2001 12:58:23 +0000
"Tom St Denis" <[EMAIL PROTECTED]> wrote in article
<VJuK6.56792$[EMAIL PROTECTED]> :
>
>" invisible inkie" <[EMAIL PROTECTED]> wrote in message
>news:9ddsje$7q3$[EMAIL PROTECTED]...
>> <delurk>
>>
>> "Tom St Denis" dropped into the real world with a crash and proclaimed...
>> >
>> > "Siva Prasad Gummadi [T]" <[EMAIL PROTECTED]> wrote in message
>> <snip>
>> >
>> > Wow you're the first person to think of a "STREAM CIPHER". I suggest
>you
>> > read some texts on crypto before declaring yourself the next Marlyn Vos
>> > Savant...
>>
>> And I suggest you read some texts on social skills before dealing with
>> people again!
>>
>> I respect your knowledge a lot, Tom, and I'm the first to admit that
>> I eagerly read your posts, because I learn a lot from them, but every
>> now and then I blow my top at your way of posting!
>
>Oh thanks. I post to share knowledge and learn at the same time. I hope
>you keep reading my posts (see below)
>
>> Siva was proposing something, and compared to other people who
>> are new here, he described it pretty seriously. He said "I think"
>> where others would've written "I know" without doing so. He didn't
>> declare himself anything, he didn't claim he'd found a golden rule,
>> he just asked for feedback, and he did it politely, ferchrissake!
>>
>> Easy on the lemming, Tom, not everyone is (yet) as knowledgeable
>> as you are! Give them some time and, what I as a teacher think even
>> more important, patience and respect. Their points might be as valid
>> as yours.
>
>You're right, people skills is not my thing. And I am always trying to be
>modest since if I ever claimed I knew everything I wouldn't need to post
>here!
>
>To Siva: Sorry I didn't mean to come off rude. No hard feelings?
>
>My original suggestion stands. I am not trying to be mean but if you want to
>be half way competent you have to read some text either AC2 or HAC.
>Otherwise you will be blundering in the dark (much like I was when I started
>posting here in 1998) and generally just getting more frustrated.
>
>Tom
>
>
It seems that what everyone is after, is a system that is as secure as an OTP, but is
able to re-use a key without losing its security....
The only way to do this, is to change something else - (other than the key), i.e the
algorithm itself, OR, add something else, with each encryption.....
Keill Randor
[EMAIL PROTECTED]
_______________________________________________
Submitted via WebNewsReader of http://www.interbulletin.com
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: A simple encryption algorithm based on OTP
Date: Fri, 11 May 2001 14:04:19 GMT
"Keill Randor" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> "Tom St Denis" <[EMAIL PROTECTED]> wrote in article
> <VJuK6.56792$[EMAIL PROTECTED]> :
> >
> >" invisible inkie" <[EMAIL PROTECTED]> wrote in message
> >news:9ddsje$7q3$[EMAIL PROTECTED]...
> >> <delurk>
> >>
> >> "Tom St Denis" dropped into the real world with a crash and
proclaimed...
> >> >
> >> > "Siva Prasad Gummadi [T]" <[EMAIL PROTECTED]> wrote in message
> >> <snip>
> >> >
> >> > Wow you're the first person to think of a "STREAM CIPHER". I suggest
> >you
> >> > read some texts on crypto before declaring yourself the next Marlyn
Vos
> >> > Savant...
> >>
> >> And I suggest you read some texts on social skills before dealing with
> >> people again!
> >>
> >> I respect your knowledge a lot, Tom, and I'm the first to admit that
> >> I eagerly read your posts, because I learn a lot from them, but every
> >> now and then I blow my top at your way of posting!
> >
> >Oh thanks. I post to share knowledge and learn at the same time. I hope
> >you keep reading my posts (see below)
> >
> >> Siva was proposing something, and compared to other people who
> >> are new here, he described it pretty seriously. He said "I think"
> >> where others would've written "I know" without doing so. He didn't
> >> declare himself anything, he didn't claim he'd found a golden rule,
> >> he just asked for feedback, and he did it politely, ferchrissake!
> >>
> >> Easy on the lemming, Tom, not everyone is (yet) as knowledgeable
> >> as you are! Give them some time and, what I as a teacher think even
> >> more important, patience and respect. Their points might be as valid
> >> as yours.
> >
> >You're right, people skills is not my thing. And I am always trying to
be
> >modest since if I ever claimed I knew everything I wouldn't need to post
> >here!
> >
> >To Siva: Sorry I didn't mean to come off rude. No hard feelings?
> >
> >My original suggestion stands. I am not trying to be mean but if you want
to
> >be half way competent you have to read some text either AC2 or HAC.
> >Otherwise you will be blundering in the dark (much like I was when I
started
> >posting here in 1998) and generally just getting more frustrated.
> >
> >Tom
> >
> >
>
> It seems that what everyone is after, is a system that is as secure as an
OTP, but is able to re-use a key without losing its security....
>
> The only way to do this, is to change something else - (other than the
key), i.e the algorithm itself, OR, add something else, with each
encryption.....
Um how we say NO!
Real ciphers are designed long the lines of fixed keys and fixed cipher
design per message. (well typically the cipher design won't change at all).
The security is suppose to lie in the key nothing more.
And real cryptographers never compare their ciphers to an OTP since it's not
a realistic thing todo. Sure there is no break against Rijndael faster than
searching the key, that doesn't make it an OTP though....etc.
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Security with provable strength.
Date: Fri, 11 May 2001 14:06:03 GMT
"Mark Wooding" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
> > Paul Rubin wrote:
> > >
> > > It was attributed in AC2 to Udi(sp?) Maurer, but it's completely
> > > insecure and there has to be some kind of mistake involved.
> > > Think linear algebra.
> >
> > Not *entirely* linear. Here it is written in psuedocode, with N=128
> >
> > These arrays are of bits:
> > K[1..N] = the secret key
> > R[1..N][1..M] = the public random strings.
> > P[1..M] = the plaintext
> > C[1..M] = the ciphertext
> >
> > for( i = 1 .. M ) {
> > x = P[i];
> > for( j = 1 .. N )
> > x ^= K[j] & R[j][i];
> > C[i] = x;
> > }
> >
> > The step with the & is *non*linear.
>
> No, it's matrix multiplication over F_2.
>
> Let K be a N-entry column vector over F_2, known to Alice and Bob.
> Alice wants to sent a message P, expressed as an M-entry column vector,
> also over F_2. She invents a random M x N matrix R over F_2, and sends
>
> C = P + R K
>
> This is the system you've proposed.
>
> Let's say we want to find K. Collect N bits of plaintext and ciphertext
> (and random strings R), and stack them all up in a column. You end up
> with a square R matrix, which you hope is invertable, and compute
>
> K = R^{-1} (C + P)
>
> Trivial.
Yup, you can solve for an unknown NxN binary matrix with N texts very
easily. You simply send in texts that have a single bit set and see what
output bits get set. You can find the transposition column by sending in
the all zero text. Voila with N+1 texts you can solve the affine case and
with N texts you can solve the linear case.
Tom
------------------------------
From: [EMAIL PROTECTED] (Bo D�mstedt)
Subject: Re: Cryptanalysis Question: Determing The Algorithm?
Reply-To: [EMAIL PROTECTED]
Date: Fri, 11 May 2001 13:12:30 GMT
Even though this is sci.crypt, let's try a systematic approach:
Can we prevent the cryptanalyst from learning which
cipher algorithm that we use?
If we do, how much can we gain?
First, we need a sufficiently large algorithm space (to prevent serial
or parallel search as discussed above). We have seen (indications on)
that this is no problem, but I feel that most readers don't think that
this is obvious at all. This is due to that most conventional block
ciphers are iterated substitution/transposition ciphers, and what
else can possibly exist??
Second we must prevent the cryptanalyst from learning which algorithm
we are using. We may use physical protection means, and zero out
the algorithm, when a physical attack is detected on a cipher machine.
(This function is advantageous anyway, and is required in FIPS 140-2
level 3-4 compliant implementations).
We may, however, annoy the cryptanalyst by using several cipher
algorithms. We may even select cipher algorithms on the fly, possibly
as a function of the IV (or similar arrangement...).
The size of the set of possible cipher algorithms, that we can select
from, will be limited to maximum available entropy. How much entropy
do we have, when encrypting? What algorithm space would that
correspond to, for a communication network? We note that if the
entropy level is estimated to be insufficient, we may use a hardware
random number generator to reach any level of entropy.
(Now the AD: http://www.protego.se/sg100_en.htm)
* * *
[EMAIL PROTECTED] wrote:
> I was giving a talk today about cryptography for my coworkers, and the
> question came up: If someone gets a chunk of cyphertext that they are
> trying to cryptoanalyze, how do they determine what algorithm was
> used, and does that even matter?
We see that not only will the cryptanalyst possibly have problems
cryptanalysing an unknown system (how much can we gain?),
but we cannot rule out actual working implementations that use
unrecoverable algorithms, based on limitations on algorithm
space and entropy.
What other limitations can there be?
And how much can we gain?
Bo D�mstedt
Chief Cryptographer
Protego Information AB
Ideon Gamma Science Park
SE - 223 70 Lund
SWEDEN
http://www.protego.se
------------------------------
** 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
******************************
