Cryptography-Digest Digest #994, Volume #11 Sat, 10 Jun 00 07:13:01 EDT
Contents:
Re: Large S-Boxes ("Scott Fluhrer")
Re: Improving DES based MAC ("Scott Fluhrer")
Re: Random IV Generation (Benjamin Goldberg)
Re: Large S-Boxes (Simon Johnson)
Re: Cryptographic voting (Greg)
Re: Cryptographic voting (Greg)
Question ([EMAIL PROTECTED])
Re: Large S-Boxes (Simon Johnson)
How does DES work? ("Michael Brown")
Re: Observer 4/6/2000: "Your privacy ends here" (Cinder)
Re: My lastest paper on Block Ciphers (Dido Sevilla)
Re: Some dumb questions (Mok-Kong Shen)
Re: Extending the size of polyalphabetic substitution tables (Mok-Kong Shen)
Re: Random IV Generation (Mok-Kong Shen)
Re: Random IV Generation (Mok-Kong Shen)
Re: Arithmetic Coding (Tim Tyler)
Re: Arithmetic Coding (Tim Tyler)
Re: Some dumb questions (Mok-Kong Shen)
----------------------------------------------------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Large S-Boxes
Date: Fri, 9 Jun 2000 22:31:06 -0700
Simon Johnson <[EMAIL PROTECTED]> wrote in message
news:8hrtja$nte$[EMAIL PROTECTED]...
>
>
> I think i'm flogging a dead-horse here, but i'm after evidence in 'a
> dummies guide to' style to the pro's and con's of randomly generated S-
> boxes.
>
> I'm thinking 16x16 for a block-cipher i'm devolping (don't hold u're
> breath, i don't have 1/2 a clue what i'm doing :), i just having fun.)
So, you're think about an sbox that will take 128k of memory? Well, that'll
work in the sense that (with high probability) there won't be any
troublesome characteristics, however, an sbox that big won't fit in a
conventional L1 cache. Assuming you're running it on any modern CPU, any
sbox reference will take several cycles while the CPU waits for the memory
(or more likely, the L2 cache) to retrieve it. Since this will happen to
almost every sbox reference, you're performance is likely to be dreadful,
and as has been pointed out, a secure block cipher is actually pretty easy
to design if you are willing to settle for dreadful performance...
--
poncho
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Improving DES based MAC
Date: Fri, 9 Jun 2000 22:45:20 -0700
Tor Rustad <[EMAIL PROTECTED]> wrote in message
news:cPj05.23560$[EMAIL PROTECTED]...
> "Scott Fluhrer" <[EMAIL PROTECTED]> wrote in message
>
> > The computational costs for 3 key 3DES is no less than for 2 key 3DES,
and
> > in many applications, the additional key bits are available anyways.
> Since
> > 3 key 3DES is believed to be strictly more secure than 2 key 3DES, and
has
> > (for those "many applications") no disadvantages, why go with 2 key
3DES?
> >
> The point is that in hardware devices, NVRAM space can be very restricted,
> going from single DES to 2K3DES, double the space requirements already. If
I
> can't hold the key table inside NVRAM, then I need to export/import DES
key
> to external storage, that means extra DES encryption/decryption, which
will
> hurt performance badly...
Key table? If you are in hardware, then you can do key expansion on the
fly -- DES was, after all, designed to be implemented easily in hardware.
And so, we are talking about the relative costs of storing 112 vs. 168 bits.
(If, by key table, you meant the actual key, my apologies...)
And, if you have 'external storage' available, why are we talking about
NVRAM? Why do you need RAM that retains it's contents on power-loss if a
copy of the key is available in "external storage"?
>
> > None of these is much stronger than DES -- they can all be broken in
> > O(2**64) operations, with neglicable memory, and 2 known
> plaintex/ciphertext
> > pairs. To take case b, you take your known plaintext/ciphertext pairs
> > (P1,C1) and (P2,C2), and rearrange the equations:
> >
> > C1 = k2 XOR (DESk( k XOR P1 ))
> > C2 = k2 XOR (DESk( k XOR P2 ))
> >
> > C1 XOR C2 = DESk( k XOR P1 ) XOR DESk( k XOR P2 )
> >
> > Then, you iterate through the various possible values of k until you
find
> > values that satisfy this last equation.
> >
> I did not see the above, nice! So you are stating that the strenght of
>
> C = k XOR (DESk( k XOR P ))
>
> is 2^64?
To be precise: at most 2^64. I am not claiming that this is the best
possible attack...
>
> Is that also the case if one of the XOR operations are removed?
No. If you remove one of the XORs, it drops to 2^56, as follows (assuming
the first xor is dropped, the second xor is similar):
C1 = k2 XOR (DESk( P1 ))
C2 = k2 XOR (DESk( P2 ))
C1 XOR C2 = DESk( P1 ) XOR DESk( P2 )
Iterate through the possible values of k -- there are only 2^56 of them. I
will be bold enough to claim that this within a constant factor of the best
possible attack, given that DES is treated as a keyed random permuation.
--
poncho
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Random IV Generation
Date: Sat, 10 Jun 2000 06:02:07 GMT
David A. Wagner wrote:
>
> In article <qPY%4.1111$[EMAIL PROTECTED]>,
> Adam Durana <[EMAIL PROTECTED]> wrote:
> > An initialization vector (IV), does not need to be generated by a
> > secure random number generator. It does not even need to be random.
> > It just has to be unique for each message.
>
> This is a common myth, but it's not true. Consider CBC mode, where
> C[i] = Encrypt(C[i-1] xor P[i]), and C[0] = IV.
What if C[0] = Encrypt(IV) ? This is very little extra work, and
prevents the attack you just described.
------------------------------
From: Simon Johnson <[EMAIL PROTECTED]>
Subject: Re: Large S-Boxes
Date: Sat, 10 Jun 2000 06:04:40 GMT
In article <8hs3v4$35n$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (David A. Wagner) wrote:
> In article <8hrtja$nte$[EMAIL PROTECTED]>,
> Simon Johnson <[EMAIL PROTECTED]> wrote:
> > I think i'm flogging a dead-horse here, but i'm after evidence in 'a
> > dummies guide to' style to the pro's and con's of randomly
generated S-
> > boxes.
>
> Don't hold your breath waiting for ``a dummy's guide to cipher
design.''
> There's no such thing, and for a good reason. Cipher design is
subtle,
> and designing ciphers without any training in the field invites
disaster.
Disaster - Nah, its a disaster if people use you're cipher, thinking
its secure, when really it isn't. There is no harm to trying to futher
your knowledge by designing ( and breaking ) a few of your own ciphers.
> This truly isn't meant as a flame, but if you think you need such a
> ``dummy's guide'', you might take that as a hint that you probably
> shouldn't be doing cipher design!
hmmm, no. Its the reason I should be doing cipher design - There is
no teacher more valuable than your mistakes. I'm sure Rivest learned
alot from RC1 & RC3!
Its ironic really, the subtly of cipher design is not being able to
construct the cipher, its being able to analyse the cipher you have
created. I know for a fact that no-one here is fully capable of that,
otherwise you wouldn't be here, you'd be off in the NSA with all the
other hamsters.
Should we all just throw in the towel because where not best in our
field?
I think not, i'm sure many posters will agree with me.
My original 'dumbies guide' post was prehaps the wrong words to use,
rather i require a wedge to break into the art of analysing math-made
ciphers.
Basically, i'm looking for a medium-paced introduction to math based
cryptanyalisis. Any offers?
--
Hi, i'm the signuture virus,
help me spread by copying me into Signiture File
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Greg <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Cryptographic voting
Date: Sat, 10 Jun 2000 06:40:05 GMT
> One of the problems such a system causes is instability.
> A stable system requires a degree of hysteresis so that
> small oscillations in voter sentiment do not produce
> large changes in the government. This is one reason that it
> takes a higher percentage to remove an official than to elect him.
This can be the case in my hypothetical government structure.
> Another problem with similar systems is that there is no
> practical limit to the power of the executive. It is much
> like a monarchy in which everyone knows who is accountable
> (the king), and what his duties are (to protect the
> subjects), but there is no mechanism by which a tyrannical
> king can be removed if he keeps his small constituency
> (classically the nobles; your senate) happy.
Thus, the one year term for the senators and NO chance they can ever
return.
>
> The worst problem with this style of government is that
> it tends to be a popular democracy. All such systems
> become oppressive due to "the tyranny of the majority".
That's why the constitution to keep the king in check. The purpose of
the "king" factor was to eliminate the blame game. That is what has
allowed Clinton to mess with America and get away with it. There are
too many people that like him to the point of blind loyalty - willing
to believe that the GOP is responsible for everything Clinton has
failed at.
--
Tyranny is kept at bay by guns and will. Our government
knows we have the guns, but they don't know if we have
the will. Nor do we.
The only lawful gun law on the books- the second amendment.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Greg <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Cryptographic voting
Date: Sat, 10 Jun 2000 06:45:27 GMT
> That should be your first clue that the "gunners" in the U.S.A. are
> those who put the right to own weapons of distruction before all
other
> rights, even the right to life.
Then I have to disagree with the initial premise...
--
Tyranny is kept at bay by guns and will. Our government
knows we have the guns, but they don't know if we have
the will. Nor do we.
The only lawful gun law on the books- the second amendment.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Question
Date: Sat, 10 Jun 2000 07:48:35 GMT
how do you find out an algorithm of a file that you cannot compare to
with samples from the program it was encrypted with. I cant use
dictionary files or the brute force method to decrypt it. I would
appreciate any help i could get thank you.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Simon Johnson <[EMAIL PROTECTED]>
Subject: Re: Large S-Boxes
Date: Sat, 10 Jun 2000 08:18:42 GMT
In article <8hsknh$bov$[EMAIL PROTECTED]>,
"Scott Fluhrer" <[EMAIL PROTECTED]> wrote:
>
> Simon Johnson <[EMAIL PROTECTED]> wrote in message
> news:8hrtja$nte$[EMAIL PROTECTED]...
> >
> >
> > I think i'm flogging a dead-horse here, but i'm after evidence in 'a
> > dummies guide to' style to the pro's and con's of randomly
generated S-
> > boxes.
> >
> > I'm thinking 16x16 for a block-cipher i'm devolping (don't hold u're
> > breath, i don't have 1/2 a clue what i'm doing :), i just having
fun.)
>
> So, you're think about an sbox that will take 128k of memory? Well,
that'll
> work in the sense that (with high probability) there won't be any
> troublesome characteristics, however, an sbox that big won't fit in a
> conventional L1 cache. Assuming you're running it on any modern CPU,
any
> sbox reference will take several cycles while the CPU waits for the
memory
> (or more likely, the L2 cache) to retrieve it. Since this will
happen to
> almost every sbox reference, you're performance is likely to be
dreadful,
> and as has been pointed out, a secure block cipher is actually pretty
easy
> to design if you are willing to settle for dreadful performance...
>
> --
> poncho
I never even considered that. I suppose the real question is two block
thru an 8x8 faster than one block thru a 16x16? Another important, and
linked, question is how long does it take to retreive from the L1 cache?
Moreover, won't the operating system be using this cache?
These points considered, it looks like the signs point to an optimized
s-box. The problem with this approach is i don't even know where to
start.
--
Hi, i'm the signuture virus,
help me spread by copying me into Signiture File
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Michael Brown" <[EMAIL PROTECTED]>
Subject: How does DES work?
Date: Sat, 10 Jun 2000 09:14:39 GMT
Hi there,
I was reading about DES's insecurities and wondering a bit about how it
works. I read somewhere else that it "folds" up the string of bits or
something, and was wondering if it is something like this: each bit
specifies a command, for example 0=swap each bit with its neighbour to the
right, 1=swap each bit with its neighbour to the left, so a 56 bit key
would have 56 "instructions". Is is instruction based, or something
completely different. If it's different, are there any other encryption
things that use this method (there seems to be a <lot> of different ones
mentioned...) or a similar one (eg:16 instructions)?
Any pointers to DES info also appreciated.
Regards,
Michael Brown
--
Hi, i'm the signuture virus,
help me spread by copying me into Signiture File
------------------------------
From: [EMAIL PROTECTED] (Cinder)
Subject: Re: Observer 4/6/2000: "Your privacy ends here"
Date: Sat, 10 Jun 2000 17:11:14 +0800
In article <[EMAIL PROTECTED]>, Paul Shirley
<[EMAIL PROTECTED]> wrote:
> In article <[EMAIL PROTECTED]>, Mok-Kong Shen <mok-
> [EMAIL PROTECTED]> writes
> >Much better: Include several lines of random hex digits that look like
> >the ciphertext of some top secrets. I posted this scheme sometime
> >back in sci.crypt.
>
> Or better yet: construct a program to create random messages wrapped to
> look like ciphertext based on a key. You can safely tell the plods
> there's no key... (or even give them it: it won't decode anything;) yet
> prove to a court the 'message' is random by regenerating it.
>
> Remember: one of the problems with this law is the presumption of guilt,
> ensuring a defence is vital in any attempt to wreck it.
What about a program which encrypts 2 files at once using different keys?
If only one file is specified, it encrypts a random string with a random
key instead. Presumably you could then say that you only had one file
encrypted, so you don't know the second key.
------------------------------
From: Dido Sevilla <[EMAIL PROTECTED]>
Subject: Re: My lastest paper on Block Ciphers
Date: Sat, 10 Jun 2000 18:40:15 +0800
tomstd wrote:
> >
> >Can I suggest that you use a file format that 1) is portable,
> and 2) less
> >hostile?
>
> At: http://wheel.compose.cs.cmu.edu:8001/cgi-bin/browse/objweb
>
> You can translate documents, I don't guarantee it will format my
> file properly... if you must there is an unzipped copy of the
> paper at
>
> http://tomstdenis.com/ffunctions.doc
>
> it's in word97 (ms-word) format.
Jeez, I mean, how hard is it to get Word97 to save a document in an open
format like HTML or PostScript? I don't own a copy of Word97 (which is
probably M$'s submission to the AES!), and so your file might as well be
in some unbreakable cryptosystem. I believe there are commands that
allow you to save a Word document to PostScript, which is, after all,
the canonical file format used for scientific papers.
--
Rafael R. Sevilla <[EMAIL PROTECTED]> +63 (2) 4342217
Mobile Robotics Laboratory +63 (917) 4458925
University of the Philippines Diliman
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Some dumb questions
Date: Sat, 10 Jun 2000 13:04:58 +0200
"Douglas A. Gwyn" wrote:
> There is a good practical codebook breaking exercise in the Zendian
> problem. (If anybody has figured out the mapping between the code
> word sequence [against the plaintext dictionary] and the code words
> themselves, I'd appreciate hearing it. That would enable a great
> deal more progress to be made past the point where most of us have
> gotten.)
It is a good point of you that there are yet classical stuffs that are
worthy of very serious study. In all human activities, fashion and
trend generally lead to oblivions and obsoletions that may not
always be fully justified. However, psychology seems not to be
the single factor that plays a role thereby.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Extending the size of polyalphabetic substitution tables
Date: Sat, 10 Jun 2000 13:05:08 +0200
"Douglas A. Gwyn" wrote:
> Mok-Kong Shen wrote:
> > ... That is not to imply at all that their design is simple but
> > only that high quality S-boxes are well within the current state of
> > the art ...
>
> You're "begging the question". On what grounds do you say that
> those [AES] S-box sets are "high quality"? Maybe they aren't, in
> which case that would support the position you're arguing against.
Certainly you are right in doubting the 'high quality' of S-boxes of
the AES candidates. Unless proved, it is indeed un-scientific to
assume that. I was taking a heuristic standpoint and considered that
these S-boxes are o.k., since the experts haven't yet been able to
find essential weakness in them. On the other hand, someone
in our group haspreviously expressed the view that, at the time
point of release of AES, its analysis period is not sufficiently long
to exclude an eventual possible surprise. (If I were ever to use
AES, I would attempt to implement variable number of rounds,
and possibly also cipher stacks using the other finalists in the
contest, in order to better cope with my unfortunate paranoid
fear of insecurity of encryption systems.)
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Random IV Generation
Date: Sat, 10 Jun 2000 13:07:31 +0200
"David A. Wagner" wrote:
> Here's one reason to be cautious. If you instead use the _decryption_
> of a counter as the IV, things are not ok. The problem in such a case
> is that you're using the same key for both IV generation and message
> encryption.
Could you explain that a little bit? Thanks.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Random IV Generation
Date: Sat, 10 Jun 2000 13:05:21 +0200
Terry Ritter wrote:
> Counter mode with a binary counter seems to be just asking for
> trouble. One alternative would be to use a polynomial counter, to get
> about half the "counting" bits to change on each count, which should
> be a lot less risky.
Sorry for my ignorance. What is the definition of a polynomial counter?
Thanks.
M. K. Shen
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Arithmetic Coding
Reply-To: [EMAIL PROTECTED]
Date: Sat, 10 Jun 2000 10:35:04 GMT
tomstd <[EMAIL PROTECTED]> wrote:
: In article <[EMAIL PROTECTED]>, Tim Tyler <[EMAIL PROTECTED]> wrote:
:>tomstd <[EMAIL PROTECTED]> wrote:
:>: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY) wrote:
:>:>[...] matt's site that has the best info on useful with
:>:> source code adaptive unadulterated arithmetic coding. [...]
:>
:>: To the best of my knowledge no arithmetic coder adds anything
:>: that doesn't need to be there. So your logic is flawed my friend.
:>
:>What if the arithmetic stream does not terminate on a byte boundary?
:>
:> Think about it - an arithmetic coding stream is pretty good -
:> but it is only rarely as perfect as you will find at:
:>
:> http://www3.sympatico.ca/mtimmerm/biacode/biacode.html
: While your site looks nice, it's pure crap. [...]
It's not my site. It belongs to Matt Timmermans (http://www.timmermans.org/)
: Nowhere in any OS does it state that your file must contain at least or a
: boundary of 8 bits of *information*.
What is the purpose of this statement? Most modern OSs enforce an 8-bit
*data* alignment. Compression produces a stream of *data*. It's
information-content from the perspective of some observer is moot.
: Note: It is possible to write 7 bits of *information* to a file
: using ms-dos for example, you just end of wasting the last bit.
So - if I have this straight - you're advocating padding out the file with
an "impossible" token that takes the last arithmetic coding symbol beyond
the EOF?
This is likely to allow analysts to reject decrypts as being invalid
compressed files - and increases the average length of the file compared
to what's possible with Matt's end-treatment. There seem to be no
compensating advantages.
: All real arithmetic coders do is calculate the high/low and when
: they match in the upper decimal (bit) they shift the bit out.
: This isn't secret hidden information, it's part of the bloody
: number!!!
Your objection here appears to be addressing a point nobody ever raised.
The only "problem" with added information in arithmetic coding schemes
occurs at the end of the file.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Breast is best.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Arithmetic Coding
Reply-To: [EMAIL PROTECTED]
Date: Sat, 10 Jun 2000 10:40:57 GMT
(SCOTT19U.ZIP_GUY) wrote:
:[EMAIL PROTECTED] (Tim Tyler) wrote in <[EMAIL PROTECTED]>:
:>What if the arithmetic stream does not terminate on a byte boundary?
:>
:> Tim the converting of a stream of bits that is not
:> constrained to byte boundaries is not that hard of problem. You can
:> find programs to handle that at Matts site or mine. In Matt's case he
:> assumes a infinte string of zero bits at the end. I am not sure why you
:> are asking this question.
I'm aware of this - I intended to direct the question at Tom, who seems
to think there's no problem at the EOF - even without special
end-treatment.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Be good, do good.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Some dumb questions
Date: Sat, 10 Jun 2000 13:10:04 +0200
John Savard wrote:
> Mok-Kong Shen<[EMAIL PROTECTED]> wrote, in part:
>
> >Yes, you get the xor of two messages. But how to go further from
> >that point (there is no known plaintext whatever)?
>
> Well, if it is a misused one-time-pad, one does not assume any other
> encipherment. If there were not even any compression applied to the
> messages, then certain things would stand out.
>
> In ASCII: control characters start with 000, spaces and most
> punctuation start with 001, uppercase letters start with 010,
> lowercase letters start with 011.
[snip]
Thanks for the valuable demonstration which supports the
essential result hitherto obtained in this thread that
in order to take care of accidental misuse frequency
flattening is a necessity and that my original conjecture
of sufficiency of a transpositon is false.
In the case of Venona, a codebook was employed that gave
decimal digits. This, if I don't err, is in general more
difficult to exploit through frequency distributions.
It might perhaps be speculated that even the introduction
of a transposition could have eventually improved the
system beyond the reach of those who had attained the
spectacular break.
M. K. Shen
------------------------------
** 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
******************************
