Cryptography-Digest Digest #646, Volume #11 Thu, 27 Apr 00 13:13:01 EDT
Contents:
Re: sboxes for the bored... (Tim Tyler)
Re: OAP-L3: Semester 1 / Class #1 All are invited. ("Trevor L. Jackson, III")
Re: "No adjacent image" hash assumption? (Anton Stiglic)
Re: factor large composite (Joe Leherbauer)
Re: Checksum algorithm which is ASCII (Michael Wojcik)
Re: Checksum algorithm which is ASCII (Michael Wojcik)
Re: Looking for a *simple* C Twofish source (Eric Lee Green)
Re: papers on stream ciphers (David A. Wagner)
Re: U-571 movie (Joseph Reuter)
Re: Looking for a *simple* C Twofish source (Eric Lee Green)
Re: Help: encrypting bit fields (Paul Rubin)
Re: Career Opportunities @ Cloakware (Eric Lee Green)
Re: sci.crypt think will be AES? (Paul Koning)
Re: Help: encrypting bit fields (Paul Rubin)
----------------------------------------------------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: sboxes for the bored...
Reply-To: [EMAIL PROTECTED]
Date: Thu, 27 Apr 2000 16:00:50 GMT
Terry Ritter <[EMAIL PROTECTED]> wrote:
: in sci.crypt Tim Tyler <[EMAIL PROTECTED]> wrote:
:>Large s-boxes take up too much space in hardware, and chew up your cache
:>in software.
: An 8-bit s-box only takes 256 bytes.
That's true. There are several ways to look at this. On one hand an
8-bit s-box isn't *terribly* large.
On the other hand, it's quite a lot bigger than a four bit one. onsider
that a 4-bit s-box takes up 8 bytes. That means you could fit about 32 of
them into the same space as a single 8-bit s-box. It also means that they
are likely to go about 5-6 times faster when implemented on a
two-dimensional substrate.
:>If you use enough independent small s-boxes in series the resulting system
:>can still be made quite strong.
: Chaining substitutions in sequence just produces another substitution.
: No possible sequence of 4-bit substitutions can be any different than
: some other 4-bit substitution.
That's not what I was trying to say. If you are making larger
permutations out of smaller ones you could use (for example) a "brickwall"
partitioning arrangment - i.e.
|v v v v v v v v v v v v v v v v|
|X X X X|X X X X|X X X X|X X X X|
|v v v v v v v v v v v v v v v v|
|X X|X X X X|X X X X|X X X X|X X|
|v v v v v v v v v v v v v v v v|
|X X X X|X X X X|X X X X|X X X X|
|v v v v v v v v v v v v v v v v|
|X X|X X X X|X X X X|X X X X|X X|
|v v v v v v v v v v v v v v v v|
|X X X X|X X X X|X X X X|X X X X|
|v v v v v v v v v v v v v v v v|
|X X|X X X X|X X X X|X X X X|X X|
|v v v v v v v v v v v v v v v v|
Data flows in at the top and out at the bottom.
Xs represent bits. One "|X X X X|" represents a 4-bit permutation.
Here the layers are applied in series (like rounds) to produce a
"simulated" 16-bit permutation. There aren't enough layers in the above
diagram to get proper diffusion from the top-left most bit in the input to
the bottom-right-most one - but you probably can see the idea I was trying
to convey.
Using this sort of idea you could build a type of 16-bit s-box which
would work much faster and take up /much/ less area than a "real"
LUT-based one. You could vary the security level quite smoothly by
adding more layers.
: And no 4-bit substitution has a nonlinearity over 4. That means that
: changing only 4 bits in the Boolean function for some bit position
: will yield a linear Boolean function.
: In contrast, it is difficult to even *find* an 8-bit substitution with
: a nonlinearity below 78.
Well, it's /easy/ to "find" such a function - provided you're not doing a
completely blind search ;-)
[making large permutations out of smaller ones]
:>The disadvantage is probably additional concern over security as a result
:>of the greater structure involved.
: I think that is exactly backwards: There is much less "structure" in
: a random 256-byte table than in a random 16-nybble table. That's what
: linearity means.
Again, I probably wasn't very clear in saying what I meant. A "genuine"
8-bit s-box made with a 256-bute LUT is maximally difficult to crack.
I was considering this structure to be uniform and flat - it's just a
simple look-up table.
A /simulated/ 8-bit s-box made up of a dozen or so 4-bit s-boxes may work
faster and take up less space, but it's probably not as secure. It has
more "structure" - in that it can be divided into a series of
partially-independent components.
Anyway, the security concern seems real enough. If using multiple small
s-boxes is a viable approach, care will need to be taken to ensure that
the difference between a real 8-bit s-box and the simulated one which is
composed of samller, more atomic components is not one on which practical
attacks can be based.
:>If a block cypher is usually a large permutation constructed from smaller
:>ones, it seems sensible to ask how large the smaller components should be.
:>
:>The possible answers seem to be "as small as possible while retaining
:>non-linearity" - i.e. 3x3 or possibly 4x4 - "as large as possible
:>without slowing things down to a crawl" - or "of a variety of sizes".
: First, none of this works unless you have some sort of mixing which
: does in fact effectively create large boxes from small ones.
Well, yes. The "brickwall partitioning scheme" I mentioned earlier would
be one approach. There are a number of other methods. Fundamentally, the
art of building large permutations from smaller ones is simply the art of
block cypher design.
: Then, to obtain simulated large boxes from small ones we need multiple
: small boxes, and a mixing process which does that. The larger the
: tables we start out with, the fewer tables and fewer mixing layers
: that are needed.
Yes, this is exactly what I'm attempting to talk about.
: My answer is: "large enough for each actual table to have substantial
: nonlinearity on its own, to protect against the case where the
: opponent reaches the actual table." Since that only needs 8-bit
: tables, which take only 256 bytes each, that seems a very reasonable
: solution.
I'm lost here. By "reaching the actual table" you /seem/ to refer to the
case where the opponent knows (or has some idea of) the relationship
between the inputs and outputs of the box. If this happens things are
not good for an s-box of 4-bits, 8-bits, or 12 bits; since in either
case the internal state is likely to be revealed with relatively little
known plaintext.
Burying each small s-box in a pile of other similar s-boxes seems
a reasonable way of stopping the opponent from "reaching the table"
in the first place.
Thanks for your comments BTW. I value your input.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Be good, do good.
------------------------------
Date: Thu, 27 Apr 2000 12:25:25 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: OAP-L3: Semester 1 / Class #1 All are invited.
Joseph Ashwood wrote:
> To everyone,
> ya know, with Szopa here I kind of miss D Scott, he
> at least had the intelligence to find new personal attacks.
You mean DS was articulate enough not to repeat himself while ASS is not?
Perhaps we should ask about the period of his posts rather than the period of
his RNG. ;-)
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: "No adjacent image" hash assumption?
Date: Thu, 27 Apr 2000 12:29:47 -0400
David A Molnar wrote:
> Hi,
>
> I was thinking about what might be useful to assume from a hash function.
>
> "No adjacent image" assumptions :
>
> Given h : {0,1}^* ---> {0,1}^k , it is infeasible to
>
> a) find two strings x and y such that abs( h(x) - h(y) ) = 1,
I guess this property would be useful if you have a scheme where you
need to visually verify a key (by it's hash) for example. What did you have
in mind?
I would think that if you could find x and y such as in a), you would be
able to find collisions (like there would be some reduction or something).
Anton
------------------------------
From: [EMAIL PROTECTED] (Joe Leherbauer)
Subject: Re: factor large composite
Date: Thu, 27 Apr 2000 16:30:10 GMT
<[EMAIL PROTECTED]> wrote:
> And again, what part of "first step" and "longer-term" is in
> dispute? The number is question is (2^773)+1, and it does
> indeed have 773-bits, with 773 > 768.
Wrong. 2^773+1 has 774 bits.
------------------------------
From: [EMAIL PROTECTED] (Michael Wojcik)
Subject: Re: Checksum algorithm which is ASCII
Date: 27 Apr 2000 15:32:47 GMT
Reply-To: [EMAIL PROTECTED]
In article <8e2dcm$8rq$[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Wim Lewis) writes:
> In article <umy9hoKr$GA.227@cpmsnbbsa03>,
> Joseph Ashwood <[EMAIL PROTECTED]> wrote:
> >I have no reason to be paid for this, as it's a very simple
> >recommendation, use SHA-1. [...]
> I think the situation is that the poster has a file with a checksum, and
> is trying to find out what algorithm produced the particular checksum.
Indeed. As was amply clear in Terry's initial post and followups.
If people would only learn to read...
--
Michael Wojcik [EMAIL PROTECTED]
AAI Development, MERANT (block capitals are a company mandate)
Department of English, Miami University
The movie culminated with a bit of everything. -- Jeremy Stephens
------------------------------
From: [EMAIL PROTECTED] (Michael Wojcik)
Subject: Re: Checksum algorithm which is ASCII
Date: 27 Apr 2000 15:38:04 GMT
Reply-To: [EMAIL PROTECTED]
In article <LzlM4.57559$[EMAIL PROTECTED]>, "Terry Neckar"
<[EMAIL PROTECTED]> writes:
> Does anyone know of a CRC algorithm that has six ASCII characters. The file
> I use is a text file similar to below. If someone has the answer, I'll
> gratefully pay them. This algorighm is at least 10 years old.
> [snip data]
> CHECKSUM: $ABCDE
Are you sure it's a CRC, and not some other kind of checksum? There
are many checksum algorithms (an infinite number, in fact) that
aren't CRCs.
Are you sure it's ASCII? IBM and some other sources use that
initial dollar sign to indicate hex numbers in some contexts, and
"ABCDE" is obviously a valid hex string. Five hex digits is a
somewhat unusual number, but there might be leading zeroes or
this checksum might be computed in, say, IBM packed decimal format
in a 6-byte field, which would produce five digits and a sign
indicator that might be discarded from the output.
Do you have any more information about what portions of the data
the checksum might cover? It's very difficult to even speculate
about it without more information.
--
Michael Wojcik [EMAIL PROTECTED]
AAI Development, MERANT (block capitals are a company mandate)
Department of English, Miami University
Even 300 years later, you should plan it in detail, when it comes to your
summer vacation. -- Pizzicato Five
------------------------------
From: Eric Lee Green <[EMAIL PROTECTED]>
Subject: Re: Looking for a *simple* C Twofish source
Date: Thu, 27 Apr 2000 16:38:22 GMT
Anton Stiglic wrote:
> The source code of all the AES candidates are available from NIST's
> web page:
>
> http://csrc.nist.gov/encryption/aes/round2/r2algs-code.html
At least for TwoFish, the reference version contains the following copyright
notice:
"Copyright 1998-99, Hi/fn and Counterpane Systems. All rights reserved."
It is unclear whether you can use this code for any purpose other than
evaluating the suitability of TwoFish for adoption as the AES standard.
--
Eric Lee Green [EMAIL PROTECTED]
Software Engineer Visit our Web page:
Enhanced Software Technologies, Inc. http://www.estinc.com/
(602) 470-1115 voice (602) 470-1116 fax
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: papers on stream ciphers
Date: 27 Apr 2000 09:03:49 -0700
In article <[EMAIL PROTECTED]>,
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
> Tom St Denis wrote:
> > Not really I could make a scheme that can give you a gb of key stream
> > and you still couldn't guess the next bit easily.
>
> If it is a modest-size keyed deterministic algorithm, you might be
> unpleasantly surprised. (I'm aware of some papers claiming such
> systems..)
Are you saying this is fundamental?
If you let the i-th bit of keystream be the lsb of SHA1-HMAC(key,i)
you get what appears to be a pretty good candidate for such an algorithm.
Am I missing something?
------------------------------
From: Joseph Reuter <[EMAIL PROTECTED]>
Subject: Re: U-571 movie
Date: Thu, 27 Apr 2000 09:21:44 -0700
Andrew Carol wrote:
> > The Japanese had a history of launching unannounced attacks. Ask the
> > Russians.
>
> They did after Pearl Harbor, but their war with Russia was already old
> news in the 40's and one time does not make a "history" of it.
I believe that one of the dispatches from Washington to the Pacific
commanders shortly before Dec 7, 1941, observed that "Japan has
never preceded an attack with a declaration of war." (Quoted from
memory, don't take it to the bank.)
--
Joseph A. Reuter, Wizard-in-Training [EMAIL PROTECTED]
"Olorin I was in my youth in the West that is forgotten."--Tolkien
You can't win, you can't break even, and it's the only game in town.
------------------------------
From: Eric Lee Green <[EMAIL PROTECTED]>
Subject: Re: Looking for a *simple* C Twofish source
Date: Thu, 27 Apr 2000 16:52:22 GMT
[EMAIL PROTECTED] wrote:
> I was aware of the all the free sources you've mentioned. I cannot
> compile or use things like "u4byte mk_tab[4][256]" (that's a lot of
> RAM too!), let alone "q8(q8(q8(q8(x, 4, n), 3 ,n), 2, n), 1, n)" (from
> brian gladman's implementation).
>
> The official ANSI C reference code is even worse in that sense (has ->
> pointers, a 256-byte array, "*((DWORD *)b) = Bswap(x)" etc).
There is an "optimized" version at the Counterpane site.
I am unclear what problem you are having compiling this source code. I use the
free GNU "C" compiler on Linux, Solaris, and Windows and have no such trouble.
I will, BTW, verify that at least the older version of Dr. Gladman's code was
NOT big-endian compatible. I have not tested the newer version (note that
Solaris-SPARC is big-endian). Counterpane's example code, on the other hand,
works properly, as long as you set the appropriate endian-ness #define, which
I do using GNU 'autoconf' (a pain in the @#$%! to set up, but saves me from
writing my own endian-ness test).
> Unfortunately I am not a cryptologist and going through the Twofish AES
> paper does not help me figure out how to implement the algorithm, since
> it is missing a much-needed pseudo-code example. One has to deeply
> understand all the math details, and closely follow the figures before
> going ahead with any coding. Compare with RC6 (or TEA...)
TwoFish is a more complicated cipher than RC6, basically. RC6 goes for
elegance and simplicity, at the expense of execution time on less-well-endowed
hardware such as smart cards (there's also the whole security issue -- it's
hard to believe that something so simple could be secure -- but I'm not
qualified to comment on that). I think it was Brian Gladman who stated that he
considered TwoFish to be an "engineer's cipher", that is, a conservative
design that was put together from fairly standard parts that could be
re-configured for different environments to optimize either space or execution
time. As such, it has a certain element of clunkiness to it, much like, say, a
Mack truck might have. I.e., useful, and hauls a heavy load, but not a thing
of beauty.
--
Eric Lee Green [EMAIL PROTECTED]
Software Engineer Visit our Web page:
Enhanced Software Technologies, Inc. http://www.estinc.com/
(602) 470-1115 voice (602) 470-1116 fax
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: Help: encrypting bit fields
Date: 27 Apr 2000 16:59:24 GMT
In article <[EMAIL PROTECTED]>,
Runu Knips <[EMAIL PROTECTED]> wrote:
>Paul Rubin wrote:
>> Say I want to encrypt a bit field (37 bits, for example) and get
>> back another 37-bit field. E.g. I want to simulate a 37-bit codebook
>> cipher. Alternatively, say I want to encrypt an integer range, such
>> as 10-digit decimal integers.
>
>Can anyone explain to me why he doesn't just use CFB mode ?
No space in the output to store an IV. Output must be same length as input.
------------------------------
From: Eric Lee Green <[EMAIL PROTECTED]>
Subject: Re: Career Opportunities @ Cloakware
Date: Thu, 27 Apr 2000 17:01:55 GMT
"Trevor L. Jackson, III" wrote:
> Marlies Vincken wrote:
> > Cloakware Corporation
> > "our revolutionary, patent-pending tamper-proof software technology"
>
> Would you care to explain this apparent silliness?
Once upon a time, I ran across a copy-protected software program that
encrypted itself multiple times. You'd unencrypt it with one key (setting your
break point in the debugger to the code right after the first unencryption
routine, of course), and the result was... yet MORE gibberish.
I think I ended up digging through 24 layers of this stuff, then there was the
code that checked checksums to look for modifications, then ....
Do note that I was doing all of this on a legally-purchased copy of the
product, and that this occurred before software vendors invented the notion of
"shrink wrap licensing" and "I Agree" boxes. (i.e., many years ago!). If
people were doing this in the early 80's, it's unclear that there's new art in
any similar obfuscation mechanisms....
--
Eric Lee Green [EMAIL PROTECTED]
Software Engineer Visit our Web page:
Enhanced Software Technologies, Inc. http://www.estinc.com/
(602) 470-1115 voice (602) 470-1116 fax
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: sci.crypt think will be AES?
Date: Thu, 27 Apr 2000 12:36:44 -0400
[EMAIL PROTECTED] wrote:
> I'm preparing a comment for NIST, but from NIST & Gladmans reports on
> speed Serpent does fair very well when you consider:
>
> 1) Hardware - Serpent faster by a fair margin.
>
> 2) Encrypting small amounts of data (where block encryption costs are
> overshadowed by key set-up costs). IMHO, bulk encryption is relatively
> rare compared to the encryption of small number of blocks (think ATM,
> IPSEC etc - these are the environments where throughput really matters.
Are you mixing up key agility with key setup?
IPSec and similar applications where many sessions are active
simultaneously require key agility: you have to be able to switch
from one key to another quicky, at each packet boundary.
But that doesn't mean you go through key setup every time.
So long as you can schedule the key ahead of time, and the
space required to store a scheduled key is modest even when
you run the cipher in its fastest mode, you're all set.
For example, what hurts Blowfish is not that the key setup
is very slow, but that the amount of space needed to store
the scheduled keys is too large. On the other hand, RC-4
is fine (with respect to this issue); while key setup is
slow, the scheduled key is only 256 bytes, which is not
too outrageous. (I'm not sure how Twofish fares here;
certainly better than Blowfish.)
The above assumes you don't do silly things like renegotiate
a new IPSec data key every 2 packets. Getting a new key
requires public key algorithms, Diffie-Hellman, and stuff
like that. Any plausible key setup time is in the noise
compared to that...
paul
--
!-----------------------------------------------------------------------
! Paul Koning, NI1D, D-20853
! Lucent Corporation, 50 Nagog Park, Acton, MA 01720, USA
! phone: +1 978 263 0060 ext 115, fax: +1 978 263 8386
! email: [EMAIL PROTECTED]
! Pgp: 27 81 A9 73 A6 0B B3 BE 18 A3 BF DD 1A 59 51 75
!-----------------------------------------------------------------------
! "A system of licensing and registration is the perfect device to deny
! gun ownership to the bourgeoisie."
! -- Vladimir Ilyich Lenin
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: Help: encrypting bit fields
Date: 27 Apr 2000 17:08:09 GMT
In article <[EMAIL PROTECTED]>,
Francois Grieu <[EMAIL PROTECTED]> wrote:
>For small message space (say up to S=64 messages) the best is probably
>to use a permutation generated using the key, among the S! possible ones.
For 37-bit messages (S=2**37), this is not practical.
>Above, an idea is to use a tailor-made Feistel cipher, using a 'known
>good' cipher as the building block. For example, assuming one wants
>to encipher a 37-bit block using DES
> split in two halves L0 (19 bits) and R0 (18 bits)
> R1 = R0 XOR low18bits(DES(K,0x2000000000000000 XOR L0))
> L1 = L0 XOR low19bits(DES(K,0x4000000000000000 XOR R1))
> R2 = R1 XOR low18bits(DES(K,0x6000000000000000 XOR L1))
> L2 = L1 XOR low19bits(DES(K,0x8000000000000000 XOR R2))
> R3 = R2 XOR low18bits(DES(K,0xA000000000000000 XOR L2))
> L3 = L2 XOR low19bits(DES(K,0xC000000000000000 XOR R3))
>with result in L3 R3.
I assume you meant to mask off the upper 64-(18 or 19) bits of
the DES output at each round--or did I misunderstand the idea?
I'm concerned that with such small blocks, collisions in the round
function can leak information about the input through to the output.
Adding rounds might take care of the problem.
Thanks for the thought though.
------------------------------
** 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
******************************
