Cryptography-Digest Digest #109, Volume #11 Sat, 12 Feb 00 19:13:01 EST
Contents:
Re: YACM - Yet Another Chaining Mode (zapzing)
Re: BASIC Crypto Question (wtshaw)
Re: UK publishes 'impossible' decryption law (zapzing)
Re: BASIC Crypto Question (wtshaw)
Re: Period of cycles in OFB mode ("Scott Fluhrer")
Re: Latin Squares (was Re: Reversibly combining two bytes?) ("r.e.s.")
Re: Which compression is best? (Jerry Coffin)
Re: Does hashing an encrypted message increase hash security?
([EMAIL PROTECTED])
Re: Period of cycles in OFB mode (Tim Tyler)
Re: Block chaining (Tim Tyler)
----------------------------------------------------------------------------
From: zapzing <[EMAIL PROTECTED]>
Subject: Re: YACM - Yet Another Chaining Mode
Date: Sat, 12 Feb 2000 22:13:34 GMT
In article <[EMAIL PROTECTED]>,
Sander Vesik <[EMAIL PROTECTED]> wrote:
> Yet Another Chaning Mode - CfBC
>
> Probably mainly of interest to anybody collecting various
non-defective
> chaining modes. It 'hides' plaintext structure somewhat better than
> CBC, while requiring more work on encryptionm and decryption.
>
> Let:
> P_n - n-th plaintext to be enciphered
> C_n - n-th ciphertext
> IV_n - n-th 'derivate' of the initalisation vector
> E_k - encryption with key k
> D_k - decryption with key k
>
> Encryption:
> IV_0=E_k(IV)
> IV_n=E_k(IV_(n-1))
> C_n=E_k(P_n ^ IV_n)
>
> Decryption:
> IV_0=E_k(IV)
> IV_n=E_k(IV_(n-1))
> P_n=D_k(C_n) ^ IV_n
>
> Propeties:
>
> DRAWBACK - divulges cyphertext at double rate.
>
> 1) hides plaintext structure well
> 2) blocks are chained, blocks cannot be inserted by a 3rd party in the
middle
> of the stream even if that party knows the key
> 3) in hardware can be implemented in parrallel, requiring about twice
the
> resources for no speed-down, in software runs at half the speed of an
> interleaved implemetation
> 4) adds an additional tiny amount of security above just plaintext
structure
> hiding.
>
> --
> Sander
>
> There is no love, no good, no happiness and no future -
> these are all just illusions.
>
What you have essentially done is created
a poor PRNG for the IV_i series.
It is poor (IMHO) because it could have
short cycles, and it could have
short cycles for some key-IV
pairs and not others.
I have always thought this would be
a good idea, though, and it is similar:
C_i=E_k(P_i^IV_i)
IV_(i+1)=H(IV_i + P_i + i)
where, in addition to your notation,
H is some hash function, and
the "+" operator indicates
catenation.
i could be expressed in a fixed
number of bits (i.e., with leading
zeros), or in "free form"
(however many bits it has, that's
how many it is expressed in).
For the latter, you would need to
have a hash function that could handle
variable length blocks.
But what would we call it?
Oh no, we could run out of letters!
--
Do as thou thinkest best.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: BASIC Crypto Question
Date: Sat, 12 Feb 2000 15:40:13 -0600
In article <[EMAIL PROTECTED]>, Johnny Bravo
<[EMAIL PROTECTED]> wrote:
> There are text only ciphers, but as a general rule they are easy to
> break, and are rather old. Newer ciphers encrypt anything into binary
> data, you could use UUencode to convert it back and forth to ascii within
> you program if necessary, but simple binary attachments via email are much
> less work.
The general rule is just that, not always true at all. Newer ciphers are
not necessary all binary either. Life is simple when you ignore the ever
present exceptions that may be better than prevalent choices
>
> >Obviously data mapping is important..so with a 32 bit colour image, one
> >would want to map down the pixel...so for a 54 bit block cipher that
> >would be two pixels...i.e. no sheet mapping across pixels....
>
> I fail to see the point. The cipher has no idea what is being
> encrypted, it makes no difference if it is text, a 2 color image, a mp3 or
> a truecolor image.
Binary often presents color choices as a compromize when base 3
representation is more exact. Consider that color is in three mixed hues
in displays. So, the trit presented values are powers of three, including
9, 27, 81, and 243 for few colors. Whenever you see 256 colors, you must
ask what they are since binary at that level in not a natural fit for the
real world.
With bigger numbers you can resolve three equal outputs, but hue changes
are easily noticed in different resolutions, especially when you go to
more colors. Such changes may never get as close to the color as it
should have been in the first place.
--
If Al Gore wants to be inventor of the internet, complain that he
did a lousy job. If he admits to not doing much, complain that he
is a slacker. Now, do we want him in charge of security?
------------------------------
From: zapzing <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: UK publishes 'impossible' decryption law
Date: Sat, 12 Feb 2000 22:18:52 GMT
In article <[EMAIL PROTECTED]>,
Adam Lock <[EMAIL PROTECTED]> wrote:
> zapzing wrote:
> >
> > The police could say "prove that this
> > really is just a bunch of random numbers
> > you used as an OTP and not another
> > encrypted file.
>
> I would love to see this happen in court.
>
> Joe Bloggs downloads "EncryptoMaster" from the Internet, encrypts his
> love letters (because he shares the computer with someone else) and
then
> gets sent to jail for two years because he can't prove the other
message
> and key was generated using a PRNG and an entropy pool. That's
assuming
> Joe even knows what a PRNG is.
>
I'm sure that in England, as in America,
"ignorance is no excuse for the law".
And I really just can't see any other way
around it. *How*, after all, would the
police be able to tell an encrypted file
from random numbers, anyway, and if the
accused must *prove* his innocence, then
how would he prove that they were random
numbers and not an encrypted file?
P.S. It could also be risky to keep
things around like abstract art or
bad poetry that you composed
yourself.
> --
> Adam Lock - [EMAIL PROTECTED]
>
--
Do as thou thinkest best.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: BASIC Crypto Question
Date: Sat, 12 Feb 2000 15:51:45 -0600
In article <883c3v$ovt$[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Paul
Schlyter) wrote:
> In article <[EMAIL PROTECTED]>,
> wtshaw <[EMAIL PROTECTED]> wrote:
>
> Don't forget the gool ol' "dit", i.e. the Decimal Digit (0,1,2,3,4,5,6,7,8,9)
> which we use so often. One "dit" corresponds to 3.32192809488736 bits.
>
> And then we have sexagesimal (base 60), which we still use today when
> we're dealing with time: hours, minutes, seconds, .... Base 60 was
> popular among some very old civilizations.
>
I think of digits as always base ten, feeling that something like binary
digit is best represented by bit in the first place, etc. The dit or
digit is just one type of information unit plainly enough. I use trit for
base 3, penit for base 5, hexit for base 6, hepit for base 7, onit for
base 11, doit for base 12, lesser others being explained as bits, like
base 8 is really 3-bits. And, yes I have real life fuction algorithms
that use these unusual information units.
Pick any number base and properly say base x information units are
involved. So, for base 60, a base 60 IU is most simply called that since
60 is not a whole number power of any lesser integer base.
--
If Al Gore wants to be inventor of the internet, complain that he
did a lousy job. If he admits to not doing much, complain that he
is a slacker. Now, do we want him in charge of security?
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Period of cycles in OFB mode
Date: Sat, 12 Feb 2000 14:54:41 -0800
Tim Tyler <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> David Wagner <[EMAIL PROTECTED]> wrote:
> : Terry Ritter <[EMAIL PROTECTED]> wrote:
>
> :> It seems to me that this is yet another way of asking for trouble,
> :> especially since a fairly easy alternative exists: Simply use a
> :> polynomial counter rather than arithmetic counting.
>
> : Do you mean using a LFSR to drive the block cipher?
> : That sounds like a good idea, if it was what you meant.
>
> Use of an LFSR would lose the ability to parallelise the process properly.
Actually, it would make it only slightly trickier. Remember, an LFSR is
just
a linear transform on its bits, and so (for a fixed n) n steps of an LFSR is
also
a linear transform (using perhaps a few more gates).
So, instead of the serial implementation of:
LSFR ----> Block Cipher ----> output stream
A parallelized version would have:
LSFRn ----> Block Cipher ----> blocks (0 mod n) of output stream
LSFRn ----> Block Cipher ----> blocks (1 mod n) of output stream
...
LSFRn ----> Block Cipher ----> blocks (n-1 mod n) of output stream
where LSFRn is the original LSFR with the linear equations modified to step
by
n every block.
Then, you initialize the LSFRn's in the obvious way, and off you go...
(Or, if you prefer a simpler approach, implement the LSFRn as an LSFR that
you
step n times between each output)
--
poncho
------------------------------
From: "r.e.s." <[EMAIL PROTECTED]>
Subject: Re: Latin Squares (was Re: Reversibly combining two bytes?)
Date: Sat, 12 Feb 2000 15:04:22 -0800
"Michael Wojcik" <[EMAIL PROTECTED]> wrote ...
: "r.e.s." <[EMAIL PROTECTED]> writes:
: > "Michael Wojcik" <[EMAIL PROTECTED]> wrote ...
: > : [re generating Latin Squares with three permutations P (one
: > : column), R (an ordering of rotations of P), and T (a final
: > : permutation of rows)]
:
: > : Question: Is the inverse of a PRT-form square always itself a PRT-
: > : form square? More generally, are all Latin Squares in PRT-form?
:
: > "No" to the 2nd question -- we can see that not all
: > Lsquares are of your PRT form, by simply comparing
: > with the known number of Latin Squares of given order.
: > Since each Lsquare created by your PRT method is the
: > product of three permutations of 1..N, that method
: > produces N!^3 distinct Lsquares. E.g. for N=10,
: > that's ~10^20;
Sorry I didn't catch this earlier, but the number of PRT
squares is not N!^3, but N!(N-1)!f(N), where f(N)=1 for N<4,
and f(N)>1 for N>=4. (I haven't been able to deduce the
complete form of f(N).) The first two steps, PR, result
in having filled the columns with the N rotations of a
selected permutation P. Thus, col_0 could get filled in N!
ways, and for each of these there are N-1 ways that col_1
could get filled, then N-2 ways for col_2, etc, and hence
N!(N-1)! different PR squares. "By inspection" we can see
that for N<4, further permutating the rows by T introduces
no square not already possible by PR alone, but that when
N>=4, new possibilities are indeed introduced. (f(N) is
clearly not N! -- maybe someone else can see what it is?)
For example, look at all 2x2 latin squares:
01 10
10 01
P can be 01 or 10, and there are 2! ways to fill the first
column with a rotation of P. But once that's done, there's
only one rotation left for the next column, giving a total
of 2!1! cases, not 2!2!. (Obviously in this case a further
permutation of rows would produce no new cases.)
Similarly, there are only 12 3x3 Lsquares, all (3!2!=12) of
which are PR squares.
For N>=4 the situation changes such that not all of the
Lsquares are PR squares, and *presumably* not all PRT
squares are Lsquares. Since we don't know f(N), it's hard
to say much more, but I suspect N!(N-1)!f(N) will prove to
grow much less rapidly than L(n) -- but we don't even have
"computational evidence" for that, unless someone has
exhaustively computed all PRT squares for some N>3.
: > but there are in fact ~10^25 order-10
: > Lsquares. The discrepancy grows rapidly -- there're
: > "only" ~10^36 PRT Lsquares of order 15, compared to
: > an estimated ~10^86 total.
At this point, I think all we have is that N!(N-1)! is a
lower bound on the total number of PRT squares, e.g.:
N=10: 10!9! ~ 10^12 ~ 2^40
N=15: 15!14! ~ 10^23 ~ 2^77
N=256: 256!255! ~ 10^1011 ~ 2^3359
[...]
: The relatively small number of order-256 squares that are PRT squares
: (the "PRT penalty", so to speak) may not be an issue in practice,
: since there are still around 10^1520 or 2^5051 PRT squares of order
: 256.
[...]
Well, we know there are at least 256!255! ~ 10^1011 ~ 2^3359,
which is also a healthy number ;-)
--
r.e.s.
[EMAIL PROTECTED]
------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Subject: Re: Which compression is best?
Date: Sat, 12 Feb 2000 16:06:38 -0700
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
[ ... ]
> : A few people consider it extremely important, but most of us realize
> : otherwise. It's of no use at all against a known-plaintext attack.
>
> ...though it can helps no end with partial plaintexts.
As long as you define "no end" as "maybe a tiny bit", sure.
> Protecting against known /partial/ plaintexts may well be worth doing.
If it really did so, yes. It doesn't.
> Besides - it's not true that it's "no use at all" against known-plaintext
> attacks. This is true, *even* if we're talking about *complete* known
> plaintexts! ;-)
I suppose if you want to get technical, yes, it can (but doesn't
necessarily) make a _minuscule_ difference even if the entire
plaintext is known, but we're probably talking about a fraction of a
percent, and probably a pretty small fraction of a percent -- a
difference that's truly negligible when we're talking about
generalities rather than details. Even in the best case, it makes
very little difference, and in most cases it makes either none at all
or so little nobody with any sense would care at all. Adding even a
single bit to the key will make FAR more difference in nearly every
case.
> : If it's designed with encryption in mind, it can be of minimal help in
> : slowing a ciphertext-only attack. [...]
>
> It can make the difference between having a broken cypher, and a
> completely unviolated one. Isn't this what security is all about?
I have yet to see or hear you, Dave, or anybody else point out a
situation in which it makes anywhere close to that kind of difference.
> : The most fundamental problem is that it doesn't really make enough
> : difference to care about: just for example, David Scott makes much
> : of the compression method he uses, and the fact that if you decompress
> : the wrong text, it produces output that's statistically similar to
> : normal plaintext.
>
> Does he? Frankly, I don't recall the occasion.
Yes, he has.
> *I* bang on about this point - but I /never/ claim it as a propery of
> David's current Huffman scheme.
>
> I've examined its compression ratios myself and - in the version I
> looked at - they were nothing to write home about.
Apparently you didn't read what I said. It's true that his
compression ratios are lousy, but that's NOT what I was talking about.
> *Where* did David claim this for his scheme? Can you quote from the post?
I've long since gotten too sick of reading his crap to bother spending
a couple hours on Deja News to find it again. If you really care,
feel free to do so yourself.
> In case you are unaware of them, I'll give an example:
>
> Compressing in one direction only diffuses plaintext in one direction.
> This means any header to the file translates into a header in the
> compressed file.
This is simply NOT necessarily true. Just for one obvious counter-
example, there's a two-pass variant of Huffman compression in which
you collect statistics on an entire data set in the first pass, and
then do compression based on those statistics in the second pass.
Your assertions do little beyond demonstrating your ignorance.
> Consequently any known header information can be used as fuel to a
> known-plaintext attack on the subsequent encryption of the compressed file
> - since this too has a known header.
No, it doesn't, at least not necessarily. As noted above, you're
doing nothing beyond demonstrating your own ignorance.
> Since you don't seem to appreciate the benefits of the technique in
> resisting such attacks, I'm suprised that you feel that you are in a
> position to criticise it :-(
You may think appreciation is necessary. I'm convinced that knowledge
is enough to put me in a position to both criticize it, and to LACK
any appreciation for it.
The simple reality is this: if your cipher, by itself, is _extremely_
margin, it's barely possible that this method will make a tiny bit of
difference. I've never said that it made no difference at all: I've
only said that IMO, the difference is too small to care about in
nearly any case of which I'm aware. You've demonstrated nothing to
the contrary.
> : For these purposes, special forms of compression make little
> : difference. Instead, you're simply looking for whatever produces the
> : smallest output.
>
> If you don't care about compressors systematically adding information to
> the files they compress, that's your look out.
"that's your look out"? You're apparently trying your own version of
security through obscurity, saying things that simply make no sense.
> Others should be advised that there are other criteria that a good
> compressor should posess besides generating relatively small output files.
>
> Most compressors allow automated rejection of keys based on the compressed
> file alone. For non arithmetic/Huffman techniques this is often possible
> given only a small fragment of the file. It seems clear enough to me that
> as this is something that can be avoided, it *should* be avoided.
Yes and no. If that were the only available criteria, it should be
avoided. Unfortunately, it's not. If you'd ever bother to sit down
and do some of the math, you'd quickly find that the superior
compression ratio provided by a different algorithm will _usually_
make more difference. Until you do the math, and figure out the real
effect on the known-plaintext that needs to be collected, etc., you
simply can't comment intelligently on the differences involved. If
you ever do, you'll quickly find that most of your appreciation is
misplaced.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Does hashing an encrypted message increase hash security?
Date: 12 Feb 2000 15:10:13 -0800
In article <87uvov$sl9$[EMAIL PROTECTED]>,
Bill Unruh <[EMAIL PROTECTED]> wrote:
>Of course a 256 bit hash is more secure ( ie harder to find collisions
>for) than a 128 bit hash. Even say MD5(text)+MD5(ROT13(text)) would be
That's not actually true. I recently encountered a password hash function
in a commercial product which had its output in two parts; one that
provided some security, and one that provided essentially no security.
Input size was limited, and the weak half was trivial to reverse, giving
me most of the bits in the input (as a function of the remaining "unknown"
bits). Then I could use brute force on the unknown bits to find an input
for an observed output value. The hash would have been much more secure
if they'd thrown out the weak half and only stored the strong half; then
I'd have had to either analyse the strong half, or spend a lot more time
brute-forcing it. The formula you describe above, where both halves of
the hash are strong, shouldn't be any worse than just storing one half,
but if you give the attacker a really weak hash of the input, that *can*
reduce the security of a stronger hash.
I don't know if this kind of situation would be possible with "real" hash
functions; the one I was looking at was not designed by cryptographers at
even the serious amateur level, and would probably have been easy to
attack even without the "clue". Maybe you're right that with "real" hash
functions, more bits never hurt... but I'd be wary of blanket statements
like that.
Although the cryptographic aspects are quite elementary by sci.crypt
standards, the attack will be announced here when we finish writing it up.
That's expected to be in a couple weeks' time.
--
Matthew Skala "Ha!" said God, "I've got Jon Postel!"
[EMAIL PROTECTED] "Yes," said the Devil, "but *I've* got
http://www.islandnet.com/~mskala/ all the sysadmins!"
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Period of cycles in OFB mode
Reply-To: [EMAIL PROTECTED]
Date: Sat, 12 Feb 2000 23:13:28 GMT
David Wagner <[EMAIL PROTECTED]> wrote:
: In article <[EMAIL PROTECTED]>, Tim Tyler <[EMAIL PROTECTED]> wrote:
[Two lines of text reinserted here for reference]
:>:> [Counter mode] has the nice property that you can parallelize it [...]
:>: Yup. From my point of view, this is the big win of counter mode.
:> You appear to be best known as an analyst, though.
:>
:> Consequently, I'm not sure how to take this ;-)
: Take it the same way you ought to be taking everything else anyone says,
: namely, as a starting point for discussion, not as gospel truth handed
: down from the heavens.
You've taken what I said in a different way to the way I meant it -
those dratted smileys don't always help in the way I want them to ;-)
>From the point of view of an attacking analyst, it can sometimes be a plus
if some cryptographic process can be parallelised - since then they can
build a big parallel machine to break it more rapidly.
I suppose I can conclude from your response that this wasn't what you meant.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
Nice computers don't go down.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Block chaining
Reply-To: [EMAIL PROTECTED]
Date: Sat, 12 Feb 2000 23:33:53 GMT
David Wagner <[EMAIL PROTECTED]> wrote:
: In article <[EMAIL PROTECTED]>, Tim Tyler <[EMAIL PROTECTED]> wrote:
:> Note that you can use parallel processing with some chaining modes anyway.
: Apart from counter mode, which ones let you do parallel processing
: in the encryption direction? Not OFB, not CBC, not CFB. Which ones
: did I forget?
When writing this, I was (irrelevantly) thinking about decryption ;-/
However... Plaintext Block Chaining (PBC), and Plaintext FeedBack (PFB)
modes allow parallel processing in the encryption direction.
You'll need to take care that the fact that, when using these modes,
chosen plaintext attacks can directly probe the underlying cypher's
innards isn't relevant, though.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
Every time I lose weight - it finds me again.
------------------------------
** 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
******************************
