Cryptography-Digest Digest #34, Volume #12 Thu, 15 Jun 00 09:13:00 EDT
Contents:
Re: On using compression as proper means of encryption (Mok-Kong Shen)
Re: On using compression as proper means of encryption (Mok-Kong Shen)
Re: On using compression as proper means of encryption (Mok-Kong Shen)
Re: New Idea (csybrandy)
Re: New Idea (tomstd)
Re: Cipher design a fading field? (Mok-Kong Shen)
Re: Cipher design a fading field? (Mok-Kong Shen)
Re: My lastest paper on Block Ciphers (Runu Knips)
Re: Another beginner question (Runu Knips)
Re: Cipher design a fading field? (Tim Tyler)
Re: Another beginner question (Runu Knips)
Re: New Idea (Runu Knips)
salt length? ("Elros")
Re: New Idea (tomstd)
Re: Digits of pi in Twofish (Tim Tyler)
Re: salt length? (tomstd)
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: On using compression as proper means of encryption
Date: Thu, 15 Jun 2000 14:10:05 +0200
David Hopwood wrote:
> Mok-Kong Shen wrote:
> [snip]
> > Use a PRNG (crypto strength unessential) with a key as
> > seed to generate a sequence of symbols (length of sequence
> > determined by PRNG) to initialize an adaptive Huffman
> > compression algorithm, taking care that all symbols of the
> > plaintext alphabet are input at least once. The output in
> > this initialization phase is discarded. Then start feeding
> > symbols of the plaintext into the algorithm. Use the result
> > as ciphertext. Decryption amounts to a corresponding
> > decompression after doing the same initialization.
>
> This is very weak. It amounts to no more than a simple
> substitution on variable-length symbols. Frequency analysis
> can be applied almost as easily to variable-length symbols as
> it can to fixed-length symbols.
I am not sure whether analysis of variable length symbols is very
easy, if one can't readily identify where a symbol starts and ends.
Consider the block code 00, 01, 10, 11, which is of constant
length. If there is a shift of one bit position of a sequence, the
decoding is completely wrong. So in the variable length case, a
single mistake (wrong guess) should lead to comparatively more
grave consequences.
> > One can employ the scheme alone or as a component of a
> > larger scheme (multiple encryption), where we note that it
> > need not necessarily be the first component of the whole (as
> > compared to current usage of compression as pre-processing).
>
> If it is not the first component, it will expand the ciphertext
> for no real benefit.
I am not considering the 'compression effect', i.e. volume reduction.
In fact, depending on the initialization, it may well lead to expansion
even if used as the first component. One should only consider it
as an encryption and evaluate whether an expansion can be
justifiable.
> > One can also substantially boost up the scheme described
> > above with simple add-on's. Since a PRNG is available to us
> > anyway, I suggest that for this purpose we inject into the
> > output stream of compression some amount of random bits
> > at dynamically determined time points with the aid of the
> > PRNG.
>
> This does not provide any significant improvement, since the
> "random bits" would have to not collide with any valid Huffman
> output symbols (in order to allow them to be recognised by the
> receiver), and the fact that they have different frequencies
> to the valid symbols would allow them to be stripped out.
The random bits are under control of the PRNG. They are removed
on decryption so there is no interference with identification of valid
Huffman output symbols. But you do provide a good hint. A better
way of injecting random bits is not to do it in long intervals but to
do it in connection with each encoded symbol being output (both
the bits and their number are determined with the aid of PRNG).
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: On using compression as proper means of encryption
Date: Thu, 15 Jun 2000 14:09:55 +0200
Tim Tyler wrote:
> : The security of the scheme is based on the fact that the
> : opponent has no knowledge of the state of the compression
> : algorithm at completion of the initialization phase.
>
> Um - have you actually done this?
>
> I can't think why it might be strong.
>
> Try encrypting a big file of zeros using this technique :-(
Thank you for raising an interesting and valuable point. I had
not given due consideration to extreme cases as I should.
So, if the scheme is to be used alone, to be able to cope with
such cases I need somehow (no definite ideas yet) to monitor the
frequency distribution of the input and inject more random bits
when the situation is poor or else (probably easier) simply go
conservative and decide to inject a certain amount (proportional
to message length) of random bits into the output like what I
previously did in my algorithm WEAK4-EX
.
Certainly, it would be foolish claim great strength (though I don't
know yet a good way to analyze), not to say to jump to any claim
of superiority over the well-established algorithms. One of my
points is that compression techniques CAN be employed in
encryption in manners more useful than apparently considered
to be in the general opinion. Whether the scheme I proposed is
the optimal one of its genre I certainly don't know. But maybe
it still has sufficient potential of further improvements through
results of discussions in this thread.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: On using compression as proper means of encryption
Date: Thu, 15 Jun 2000 14:10:11 +0200
"John A. Malley" wrote:
> I recommend Mojdeh Mohtashemi's Master's Thesis "On the Cryptanalysis of
> Huffman Codes."
> She provides some general results on the difficulty of the
> cryptanalysis.
>
> http://theory.lcs.mit.edu/~cis/theses/mohtashemi-masters.ps
>
Many thanks for the pointer. I'll study it.
M. K. Shen
------------------------------
From: csybrandy <[EMAIL PROTECTED]>
Subject: Re: New Idea
Date: Thu, 15 Jun 2000 08:03:31 -0400
Reply-To: [EMAIL PROTECTED]
tomstd wrote:
>
> In article <[EMAIL PROTECTED]>, csybrandy
> <[EMAIL PROTECTED]> wrote:
> >I retract (hehe) what I said before about retireing from the
> cipher
> >design arena. It seems you can blame Tom for this since I got
> this idea
> >from reading his paper (which isn't too bad so far)
> >
> >What gave me this idea was when he stated that data dependent
> rotates
> >(so far) never use all of the bits in a word. That got me
> thinking, how
> >would I solve this problem? The first idea I had, assuming 32-
> bit
> >words, was to extract 6-5 bit values from a single word. This
> left us
> >with 2 bits unused, so I figured I could do better. Next I
> thought
> >about 8-4 bit values, but I figured that would be too many try
> to use
> >and would create a very slow s-box (unless you have hardware
> rotates).
> >What I finally came up with was creating 4 values by adding
> pairs of 4
> >bit values from the total of 8. Here's an example:
> >
> >& = bitwise AND
> >>> = right shift
> >
> >a1 = (A & 15) + ((A >> 4) & 15)
> >a2 = ((A >> 8) & 15) + ((A >> 12) & 15)
> >a3 = ((A >> 16) & 15) + ((A >> 20) & 15)
> >a4 = ((A >> 24) & 15) + ((A >> 28) & 15)
> >
> >Now if you add the next equation consisting of right rotates
> (>>>), left
> >rotates (<<<), additions, and exclusive or's (^), you have a
> simple
> >f-function:
> >
> >B = B + (A >>> a1) ^ (A <<< a2) + (A >>> a3) ^ (A <<< a4) + k[i]
>
> Hehehehe another weakness.
>
> Suppose a1..a4 were randomly distributed over 0..31 then
>
> 0 = (A >>> a1) ^ (A <<< a2)
>
> Would be true for all A iff a1 = 32 - a2
>
> Similarly you get very degenerative properties if a1 = a2 = a3 =
> a4 = 0, which is possible if the input A is zero by looking at
>
> >a1 = (A & 15) + ((A >> 4) & 15)
> >a2 = ((A >> 8) & 15) + ((A >> 12) & 15)
> >a3 = ((A >> 16) & 15) + ((A >> 20) & 15)
> >a4 = ((A >> 24) & 15) + ((A >> 28) & 15)
>
> Even with round keys (added to A) you can identify weak keys (a1
> = a4) with a prob of 2^-16 and it reveals 16 bits of the key.
>
> The funny thing is because you are not randomly distributed over
> 0..31 finding
>
> a1 = 32 - a2
>
> Is less probable....
>
> Hehehehe
>
> Tom
Well, it was just an example implementation of my idea. I personally
think that between the rotates there should be an s-box or something,
but I just wanted to be able to show what I meant quickly.
csybrandy
>
> * Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
> The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
Subject: Re: New Idea
From: tomstd <[EMAIL PROTECTED]>
Date: Thu, 15 Jun 2000 05:22:25 -0700
In article <[EMAIL PROTECTED]>, csybrandy
<[EMAIL PROTECTED]> wrote:
>
>
>tomstd wrote:
>>
>> In article <[EMAIL PROTECTED]>, csybrandy
>> <[EMAIL PROTECTED]> wrote:
>> >I retract (hehe) what I said before about retireing from the
>> cipher
>> >design arena. It seems you can blame Tom for this since I
got
>> this idea
>> >from reading his paper (which isn't too bad so far)
>> >
>> >What gave me this idea was when he stated that data dependent
>> rotates
>> >(so far) never use all of the bits in a word. That got me
>> thinking, how
>> >would I solve this problem? The first idea I had, assuming
32-
>> bit
>> >words, was to extract 6-5 bit values from a single word.
This
>> left us
>> >with 2 bits unused, so I figured I could do better. Next I
>> thought
>> >about 8-4 bit values, but I figured that would be too many
try
>> to use
>> >and would create a very slow s-box (unless you have hardware
>> rotates).
>> >What I finally came up with was creating 4 values by adding
>> pairs of 4
>> >bit values from the total of 8. Here's an example:
>> >
>> >& = bitwise AND
>> >>> = right shift
>> >
>> >a1 = (A & 15) + ((A >> 4) & 15)
>> >a2 = ((A >> 8) & 15) + ((A >> 12) & 15)
>> >a3 = ((A >> 16) & 15) + ((A >> 20) & 15)
>> >a4 = ((A >> 24) & 15) + ((A >> 28) & 15)
>> >
>> >Now if you add the next equation consisting of right rotates
>> (>>>), left
>> >rotates (<<<), additions, and exclusive or's (^), you have a
>> simple
>> >f-function:
>> >
>> >B = B + (A >>> a1) ^ (A <<< a2) + (A >>> a3) ^ (A <<< a4) + k
[i]
>>
>> Hehehehe another weakness.
>>
>> Suppose a1..a4 were randomly distributed over 0..31 then
>>
>> 0 = (A >>> a1) ^ (A <<< a2)
>>
>> Would be true for all A iff a1 = 32 - a2
>>
>> Similarly you get very degenerative properties if a1 = a2 =
a3 =
>> a4 = 0, which is possible if the input A is zero by looking at
>>
>> >a1 = (A & 15) + ((A >> 4) & 15)
>> >a2 = ((A >> 8) & 15) + ((A >> 12) & 15)
>> >a3 = ((A >> 16) & 15) + ((A >> 20) & 15)
>> >a4 = ((A >> 24) & 15) + ((A >> 28) & 15)
>>
>> Even with round keys (added to A) you can identify weak keys
(a1
>> = a4) with a prob of 2^-16 and it reveals 16 bits of the key.
>>
>> The funny thing is because you are not randomly distributed
over
>> 0..31 finding
>>
>> a1 = 32 - a2
>>
>> Is less probable....
>>
>> Hehehehe
>>
>> Tom
>
>Well, it was just an example implementation of my idea. I
personally
>think that between the rotates there should be an s-box or
something,
>but I just wanted to be able to show what I meant quickly.
Even if a1..a4 were totally random things like
B += (A <<< a1) xor (A >>> a2)
Is a very bad idea. For example with a prob of 1/32 you have a
weak transform (zero output) and a myrad of other problems.
My idea for RC5 was to use four 8x5 sboxes and use those to calc
the rotate. However, differntial attacks on the sboxes are all
that is stopping cryptanalysis of the entire cipher then.
Something like
B += ((((A <<< a1) + K1) <<< a2) + K2) <<< a3) + K3) <<< a4
If you could make a1..a4 randomly distributed over 0..31
(basically 20 bits) that are dependent on the plaintext that
should be ok.
However, there is a 2^-15 chance of this being totally linear
(all rotates the same). In a block cipher it would really
depend on how you get those 20 bits.
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Cipher design a fading field?
Date: Thu, 15 Jun 2000 14:37:02 +0200
Tim Tyler wrote:
> However the original question was "if program size is bounded, does the
> halting problem exist for that set of programs?"
>
> There exists a finite program that correctly states whether each program
> in such a space will terminate.
Isn't it that there exists no program that is always capable to determine
the halting property, when one arbitrarily feeds it with a program (finite
by nature of input to the checking program)? Or have I misunderstood
you?
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Cipher design a fading field?
Date: Thu, 15 Jun 2000 14:37:08 +0200
Benjamin Goldberg wrote:
> Mok-Kong Shen wrote:
> >
> > John Savard wrote:
> >
> > > Well, if the size of the RAM available to a program is limited, not
> > > just the size of the program itself, then a program with N bits of
> > > storage available to it can have only 2^N distinct states. Hence, if
> > > it doesn't halt after 2^N instructions, it is proven that it will
> > > never halt.
> >
> > You probably mean that execution of each intruction must lead to a
> > single unique successor state. How about the case that this doesn't
> > hold, i.e. when the state transition depends on the history?
>
> That would require allocating memory each time data is added to the
> history, wouldn't it?
That depends on how much history you want to consider. Compare a
Markov chain where only the immediatly preceeding state is relevant.
M. K. Shen
------------------------------
Date: Thu, 15 Jun 2000 14:27:12 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: My lastest paper on Block Ciphers
Anton Stiglic wrote:
> If you compile a .ps on one machine, you might not be able to get
> the .pdf on another.
Where did you get THAT idea ? .ps is as device independent as .dvi.
> If you start out with the .dvi format (which you get out of latex),
> then you can get a .ps and .pdf on any machine.
.ps is Postscript, and Postscript is a page description language.
The only problem you might get is if you have not stored a font in
the .ps and the other machine doesn't have it either.
------------------------------
Date: Thu, 15 Jun 2000 14:37:31 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: Another beginner question
Cheri & Mike Jackmin wrote:
> Consider a simple cipher in which SHA-1 (or a similar message digest)
> was used to generate a series of key blocks from the preceding
> ciphertext. How would this cipher be vulnerable?
I doubt you can use a one way hash function for anything but a slow
stream cipher, and who needs a slow stream cipher ?
> For example, suppose I want to encrypt a message of arbitrary length.
> I take user's the password, run it through SHA-1 to produce a 128 bit
> key, and XOR this key against the first 128 bits of the message to
> produce my first block of ciphertext. I then take this block of
> ciphertext, run it through SHA-1 to generate my next 128 bits of key,
> and so on.
First look at the first block.
The bad thing is, if you use the same key more than once, an attacker
will detect that the difference of those two initial blocks have
typical statistical properties. He will continue attacking it exactly
the same way as an OTP where the pad has been used multiple times.
As has been already mentioned in the group, every but the first block
is absolutely open to the public.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Cipher design a fading field?
Reply-To: [EMAIL PROTECTED]
Date: Thu, 15 Jun 2000 12:34:32 GMT
Trevor L. Jackson, III <[EMAIL PROTECTED]> wrote:
[much snip]
: The key question becomes whether the program can be written small enough
: to fit within itself (this is a data compression issue). If so then the
: Halting Problem can't be constructed because such a lookup program will
: halt after reporting that it will do so.
While the issue of whether the table can be compressed to the size of the
programs whose status it lists may have some curiosity value, I can't see
it as a key question - since the halting problem doesn't exist for
any particular finite set of programs anyway - regardless of how much
the list mentioned can be compressed.
There /will/ exist some (possibly very large) finite program that says
which programs from the specified finite set terminate.
This is a different case from that presented by the halting problem -
which says that no such program can possibly exist.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ VIPAR GAMMA GUPPY.
------------------------------
Date: Thu, 15 Jun 2000 14:42:22 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: Another beginner question
Simon Johnson wrote:
> Hey, i thought the author of this post was suggesting the following,
> [.... looked like:
C(0) = H(key) XOR P(0)
C(i) = H(P(i-1)) XOR P(i)
> ...]
Hmmm that would be a little bit more secure, but as I've already
shown, if someone encrypts two messages with the same key, you
can easily attack them just like an OTP which has been used
multiple times.
> I don't know, maybe i'm wrong :p
I didn't understood it that way.
------------------------------
Date: Thu, 15 Jun 2000 14:48:44 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: New Idea
csybrandy wrote:
> What gave me this idea was when he stated that data dependent rotates
> (so far) never use all of the bits in a word.
Damned, you're starting to discover things I'm using in my new version
of Whirl :) I've to release it soon, I guess ;-)
------------------------------
From: "Elros" <[EMAIL PROTECTED]>
Subject: salt length?
Date: Thu, 15 Jun 2000 08:01:43 -0500
For use with a stream cipher (e.g. RC4), what's a good length for a salt (S)
that gets concatenated (&) to the user supplied key (U) before S & U gets
fed into the cipher?
------------------------------
Subject: Re: New Idea
From: tomstd <[EMAIL PROTECTED]>
Date: Thu, 15 Jun 2000 06:02:48 -0700
In article <[EMAIL PROTECTED]>, Runu Knips
<[EMAIL PROTECTED]> wrote:
>csybrandy wrote:
>> What gave me this idea was when he stated that data dependent
rotates
>> (so far) never use all of the bits in a word.
>
>Damned, you're starting to discover things I'm using in my new
version
>of Whirl :) I've to release it soon, I guess ;-)
Well if you use rotations like Csybrandy then let me be the
first to break your cipher :)
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Digits of pi in Twofish
Reply-To: [EMAIL PROTECTED]
Date: Thu, 15 Jun 2000 12:50:55 GMT
Vernon Schryver <[EMAIL PROTECTED]> wrote:
: SHEESH!--I can't take it any longer.
: An unjustified belief in the safety, sanctity, or other wonderfulness of
: digits of pi or of the golden mean is no less of a groundless superstition
: than unjustified suspicion of evil intent in the choice of any other
: constant. If some constants are more suitable than others, then why would
: you expect arbitrary digits to among the good choices intead of the bad?
You don't. You expect them to be average - in terms of their statistical
properties.
: Can you not think of an "obvious," apparently "innocent" way to derive
: weak DES S-boxes or any other naughty value you need from the first digits
: of pi? [...]
Obviously if the construction used is convoluted, that's a cause for
suspicion. Taking the digits from PI and putting them directly into
s-boxes in the order in which they're used would probably largely avoid
this concern.
: What if you pick the first bunch of digits of pi starting after
: the 10th, 100th, 1000th, or some other "obvious" and "innocent" starting
: digit?
The more suspicious things you do, the worse it will look.
: If you were naughty and needed a trap-door constant for your evil
: cypher, do you really think you could not find it somewhere among the
: digits of the golden mean, pi, e, the speed of light, and the many other
: "innocent" constants an educated person has had to memorize by age 25?
Personally, OTTOMH, I know 23 digits of PI. No other constant comes
anywhere near this figure.
It appears to me that you're raising obscure objections by this stage.
: Never mind which constants are normal in some base of your evil choosing,
: or creativity in apparently arbitrary choices in how you convert those
: digits into binary numbers or gates.
As before, the more suspicious things you do, the worse it will look.
: On the other hand, believing the choice of one of those automatically
: confers any virtue on a cypher is silly.
I don't think thgis is right. I side with Blowfish's designers. Use of
the digits of PI has a definite and concrete virtue.
I can think of few better ways of demonstrating that you've avoided
introducing a trapdoor, if you have a large number of fixed "random"
constants in your cypher.
A public demonstration involving a real random number generator,
designed by a representatives of the potential users is another idea
that might offer some assurance - though this lacks the eternal nature of
using the digits of PI ;-)
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ VIPAR GAMMA GUPPY.
------------------------------
Subject: Re: salt length?
From: tomstd <[EMAIL PROTECTED]>
Date: Thu, 15 Jun 2000 06:07:20 -0700
In article <8iak3p$4ejql$[EMAIL PROTECTED]>, "Elros"
<[EMAIL PROTECTED]> wrote:
>For use with a stream cipher (e.g. RC4), what's a good length
for a salt (S)
>that gets concatenated (&) to the user supplied key (U) before
S & U gets
>fed into the cipher?
>
That's a stupid idea. You should feed the RC4 key schedule the
hash of the password and salt.
The salt should be long enough so that's it's never used twice
(with high probability). If you are sending a message a day
then just use the time_of_day in seconds.
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
** 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
******************************
