Cryptography-Digest Digest #785, Volume #8 Tue, 22 Dec 98 06:13:04 EST
Contents:
Re: Rules of the game (wtshaw)
Re: Rules of the game
Re: Cryptography board game! (was: CipherSaber for Dummies?) ([EMAIL PROTECTED])
Re: Hashing for randomness (STL137)
Re: RC4 in 8-bit vs 16-bit (fungus)
Enhancement of EBC mode? (Marco Stolpe)
Re: coNP=NP Made Easier? (Bryan Olson)
Re: On living with the 56-bit key length restriction (Mok-Kong Shen)
Re: HELP! Who can decrypt this? (Damian Weber)
Re: On living with the 56-bit key length restriction ("Dr.Gunter Abend")
Re: Enhancement of EBC mode? (Bryan Olson)
Meet in the middle attack? (Gramps)
Re: On living with the 56-bit key length restriction
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Rules of the game
Date: Mon, 21 Dec 1998 20:36:09 -0600
In article <75mpd3$[EMAIL PROTECTED]>, Karl-Friedrich Lenz
<[EMAIL PROTECTED]> wrote:
> In Claude Shannon's paper "Communication Theory of Secrecy Systems" (see
> Collected Papers, New York IEEE Press 1993) the author includes two references
> to game theory. The second one is in the section number 21 on "work
> characteristic" (page 132 in the IEEE edition). According to Shannon,
cryptology
> can be thought of as a zero-sum two-person game with complete information, and
> just two moves (cipher design and analysis). And the value of the designer's
> move is the avarage work required to break a cryptogram.
>
> I have a simple question about this approach. If you think of cryptology as a
> game, then what is the rule to determine the winner of that game?
>
> Karl-Friedrich Lenz
> www.toptext.com/crypto/
Shannon's theorizing was fastly outstripped by events. Since then there
has been a blossoming of algorithms that seem to defy reasonable attack
methods. Below those, some algorithms may be solvable in a range of
effort from simple recognition to requiring systematic complex
computerized brute force. Keep within those limits, and it can be a game;
go to strength beyond them, and normal analysis is insufficient to play,
and those who will play are apt to be deadly serious.
The players determine the qualifications necessary to be declared a
winner. To be a game, there must be some fun and/or reward for the
players; it can be intrinsic, just demonstrating ability to solve or foil
solution. Most fun to some are the solvables that pull some sneaky trick,
or those that require special skills. Others prefer to take on only
algorithms of a certain type of a limited complication. A few pride
themselves in being able to solve quite a range of ciphertexts.
It is not all as simple as Shannon represents, but he has tended to miss
some of the details before; when you ignore exceptions, it makes
generalizing easier, but does not necessarily prove your conclusions are
accurate, much less exclusively correct.
--
What goes around, comes around.
You reap what you sow.
Do unto others as you would have them do unto you.
The wheels of the gods grind most slowly, but exceedingly fine.
People in glass houses should not cast stones.
Let those who are without sin cast the first stone.
Judge not that ye be judged.
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: Rules of the game
Date: 22 Dec 98 03:46:09 GMT
Karl-Friedrich Lenz ([EMAIL PROTECTED]) wrote:
: I have a simple question about this approach. If you think of cryptology as a
: game, then what is the rule to determine the winner of that game?
If the cryptographer succeeds in establishing secure communications, he
wins: if the cryptanalyst obtains intelligence, he wins.
Now, in the real world, there are shades of gray, and the winner is often
not announced, but Shannon's simplified model - which he knew full well
fell short of reality - was a good starting point for his paper. Much
progress in physics and mathematics comes from starting with a model that
is known to be too simple to fully represent reality; one has to start
_somewhere_ to accomplish anything.
John Savard
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: talk.politics.crypto
Subject: Re: Cryptography board game! (was: CipherSaber for Dummies?)
Date: Tue, 22 Dec 1998 00:09:33 -0600
Robert Munyer wrote:
> I shouldn't have used the terms "five-bit" and "eight-bit." People
> will misinterpret these byte widths as key lengths, and think the
> cipher is weak. It would be better to call them the "32-square"
> and "256-square" versions of the game.
>
> The 256-square version of the game does full CipherSaber encryption,
> which of course has a very respectable key length. From over 100
> bits to over 300, depending on how you choose your key.
>
> -- Robert Munyer <[EMAIL PROTECTED]>
Hey, just skip the 32-square version, and use a 64-square version. Many
people already have one of those boards - they call it a checker (or
chess) board. I wonder if it's too difficult to expect people to do
adding and xoring in octal?
32 isn't enough if you want to have a square that represents each
alphabetic and numeric character.
--
=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/
Mark Andreas <[EMAIL PROTECTED]> http://www.sky.net/~voyageur
PGP key 77EF76B1 available via key server, finger or webpage
=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\
------------------------------
From: [EMAIL PROTECTED] (STL137)
Subject: Re: Hashing for randomness
Date: 22 Dec 1998 06:59:37 GMT
Why does everyone like MD5 when it is on its last legs.... ?
===========
[EMAIL PROTECTED] ===> Website: http://137.tsx.org <=== Find my PGP Key
Fingerprint there. Quotes: http://quote.cjb.net
"The simplest schoolboy is now familiar with truths for which Archimedes would
have sacrificed his life" - Ernest Renan
------------------------------
From: fungus <[EMAIL PROTECTED]>
Subject: Re: RC4 in 8-bit vs 16-bit
Date: Tue, 22 Dec 1998 08:35:52 -0100
Anonymous wrote:
>
> I started wondering what would happen to the relative strength of the
> cipher if the state table was instead a 65536-entry table of 16-bit
> words.
Well, you'd need some more memory...
Seriously though, the best known attack on RC4 is a brute force
attack for the entire keyspace. The limiting factor is the key
size, not the size of the internal state table. Making RC4 16
bits wouldn't give you any more security in practice.
--
<\___/>
/ O O \
\_____/ FTB.
------------------------------
From: Marco Stolpe <[EMAIL PROTECTED]>
Subject: Enhancement of EBC mode?
Date: Tue, 22 Dec 1998 09:13:31 +0100
=====BEGIN PGP SIGNED MESSAGE=====
Hash: SHA1
Hello!
I'm planning to write an application where encryption of files
is needed but random access to the content of these files is
necessary.
- From chapter nine of the book "Applied Cryptography" by
Bruce Schneier (1996) I concluded that the only thing I can
do is to use a block cipher with ECB mode. In this book the
following negative aspects of ECB are mentioned:
" 1) Plaintext patterns are not concealed.
2) Input to the block cipher is not randomized; it is the same
as the plaintext.
3) Plaintext is easy to manipulate; blocks can be removed,
repeated, or interchanged. "
Although I don't know a good solution to 3), I considered the
following solution to 1) and 2):
- - Decrease the amount of information stored in each byte,
for example by using the base64 encoding scheme.
- - Fill up the 'free' bits in each byte with random bits
produced by a very good random sequence generator
(for example the one proposed in chapter 17.14 of the
book which I mentioned).
- - Encrypt the block with a normal block cipher.
Since I'm not a professional cryptographer, I would like to
know if such a procedure could increase security of ECB mode
in any way?
I'd like to hear from you,
Marco Stolpe
- --
PGP Key, ID 0x4F3FE0B5 should be available on a keyserver
Fingerprint:
D0AA F39C 0D9D 4AC8 D742 C0DB 3536 3D29 4F3F E0B5
=====BEGIN PGP SIGNATURE=====
Version: PGPfreeware 5.0i for non-commercial use
Charset: noconv
iQA/AwUBNn9UGjU2PSlPP+C1EQI3wwCgryDeEfLncaRIi0bXrYaNioGziG4An0aD
PsYMo4YqvIfmzvS+D4swjPoW
=stKf
=====END PGP SIGNATURE=====
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Crossposted-To: sci.math,comp.theory
Subject: Re: coNP=NP Made Easier?
Date: Tue, 22 Dec 1998 01:48:32 -0800
rosi wrote:
> I think I am not confused and you are NOT ilias.
>
> I can, at this time, only answer one person, focusing on one set of
> questions and getting one thread taken care of.
Posts invite follow-ups. E-mail is the appropriate medium for
private discussions.
> One other thing, yet very important. Your interpretation and under-
> standing of ilias's notions, opinions, statements, etc. are likely
> very correct, and it will be appreciated when you try to help people
> to explain whatever they mean. However, I need his words. If you had
> joined the discussion earlier and given your opinion on 21, I likely
> could have found an ally.
There's no need to worry about Dr. Kastanas' concept versus Valmari
Antti's or Rune Bang Lyngsoe's or mine. They are the same in every
important way.
> Would you commit to carrying out this through to the end once
> we start? I.e. either we agree my argument is correct, or my
> argument is faulty, or one side is shown inconsistent or contradictory
> (if some simple questions are answered squarely and directly without
> evasion)?
>
> By the way, ilias perhaps has already seen that whichever notion
> he uses, the issue IS settled (if ND is a well defined concept).
I cannot commit to carrying through until we agree. The
significant questions have already been resolved.
[...]
> In the meanwhile, you can prepare your notion of
> a NDTM for solving SS and post for our discussion.
No need. I've adopted the same definition one finds in the
textbooks.
> You may, of course,
> choose one from 26 and 27, or give a precise one of your own (well-
> defined assumedly). You may also get ready to answer the questions I
> posed to ilias. For simplicity, you may answer in the following way:
> 1. YES
> 2. YES
> 3. NO
> 21. YES
> etc.
Neither 26 nor 27 contains a question. You defined M as a TM (not
a NDTM), that accepts SS in finite (not polynomial) time. If the
question is whether such a machine exists, of course it does. And
a machine satisfying the same criteria, but also deciding - not just
accepting - SS also exists.
--Bryan
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: On living with the 56-bit key length restriction
Date: Tue, 22 Dec 1998 10:48:42 +0100
Lincoln Yeoh wrote:
>
> I'm not in any of those 33 countries. I am very sure there are very very
> many other people who have what I have and living in less restrictive
> countries. I'm in Malaysia, and can export the stuff elsewhere. Have
> wondered what will happen if I put the stuff in Geocities. I mean it's
> perfectly legal for me. I'll just have a button saying if you are legally
> allowed to receive > 56 bit crypto click here, if not click "<56 bit". That
> should do right? I mean only crooks would click the button illegally, and
> the US gov isn't targeting crooks right? Only crooks would knowingly
> smuggle 128 bit crypto out of the country. I'm just following their logic.
>
> What do you think? Should I put it somewhere on geocities or tripod?
Wassenaar limits only export from the 33 countries, not import into
these, if I don't err. Since you are outside, you can set up an
archive with a server in that region (i.e. out of the bounds of the
power of the 33 countries) for strong crypto. In that case you don't
need to provide the button described above at all. The problem with
such an archive is maintenance, keeping the stuff up-to-date,
and general management, including what to store and whether
facility for uploading is provided, and security, including the
issue of possiblity of binaries being infected by virus as a result
of organized attacks on such an archive by those who like very
much to supress strong crypto in the technically weaker regions
of the world.
M. K. Shen
==============================================
Sunshine is the best disinfectant.
(citation of a citation in B. Schneier and D. Banisar, The Electronic
Privacy Papers. John-Wiley, New York, 1997.)
------------------------------
From: [EMAIL PROTECTED] (Damian Weber)
Subject: Re: HELP! Who can decrypt this?
Date: 22 Dec 1998 09:57:41 GMT
In article <[EMAIL PROTECTED]>,
"Rolf-Juergen Hornasek" <buddhatm.prod@technologist;com> writes:
RJRH> Is anybody able to find one of the factors (p or q) of n before
RJRH> Dec 31, 1998
RJRH> ?
RJRH>
RJRH> This is a math exercise and I can win a free lunch at a restaurant, so
RJRH> please do your best ;)
Have a fine meal.
RJRH>
RJRH> By the way, the message is one of the factors, but RSA encoded.
RJRH>
RJRH> n =
RJRH> 13258471059096133251909412192895866283659211993989463565875608267545947079653
RJRH> k = 11
77 digits is far too easy for the factoring experts and too hard for the
factoring newbies. I think I'm somewhere in between so I did this little RSA
exercise.
n factors as
p=81478455348504198953888309592613193477
q=162723642739497950570147353717875662689
(MPQS, 4 Pentium II, 4 PPro, ~6 hours)
(p-1)(q-1)=
13258471059096133251909412192895866283415009895901461416351572604235458223488
d=8437208855788448433033262304570096725809551751937293628587364384513473414947
RJRH> n is 253 Bit long, blocksize is therefore 252 Bit
RJRH>
RJRH> Message:
RJRH>
RJRH> {701844610313765365640529273403831583384392365200920477395127592866869039358
RJRH> 3,
RJRH> 8218661392572496194046556568188212507181807927737262587926561579563601454332
RJRH> ,
RJRH> 3026280963142683634569920274261272754206891892921973715968695665312611956775
RJRH> ,
RJRH> 2890830393956787255162877822922694067947480659511661703984246960098713505601
RJRH> }
m^d mod n expressed in hex and viewed as ASCII gives
4469652062656964656E2046616B746
Die beiden Fakto
F72656E206C617574656E203136323732333634323733393439373935303537
ren lauten 16272364273949795057
3031343733353337313738373536363236383920756E6420383134373834353
0147353717875662689 und 814784505
53334383530343139383935333838383330393539323631333139333437372E
348504198953888309592613193477.
which can be translated as
"The two factors are 162723642739497950570147353717875662689
and 814784505348504198953888309592613193477."
-- Damian
------------------------------
From: "Dr.Gunter Abend" <[EMAIL PROTECTED]>
Subject: Re: On living with the 56-bit key length restriction
Date: Tue, 22 Dec 1998 11:16:45 +0100
Mok-Kong Shen wrote:
> > > > > 6. Using code books.
> ... Now if for the English world one could agree
> on a not too large subset of frequently used words and give these
> fairly random numerical values, then frequency analysis based on
> single characters, bigrams, etc. will be barely feasible (for
> messages that use the said vocabulary subset). Hence the strength of
> all kinds of encryption algorithms will profit from the existence of
> such a standard code book. The practical problem is, of course, to
> design such a code book that most people would agree to use as a
> standard.
Why not using a common compression algorithm in order to make
frequency analysis unfeasible? A common prefix of the compressed data
would be some kind of "known plaintext", hence it must be avoided.
Then the only problem would be that all people should agree to use
that specific compression algorithm as a standard - even if it doesn't
append its identifying prefix to the data.
It is not necessary that this algorithm produces very good
compression. The most important feature is not the reduction of the
message size but the impossibility of a frequency test of the coded
data. Of course, this doesn't increase the key length, but it makes
brute force attacks slower.
Is there any such kind of compression algorithm that doesn't itself
produce a strongly non-random frequency distribution?
Ciao, Gunter
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Enhancement of EBC mode?
Date: Tue, 22 Dec 1998 02:10:45 -0800
Marco Stolpe wrote:
> I'm planning to write an application where encryption of files
> is needed but random access to the content of these files is
> necessary.
[...]
> I concluded that the only thing I can
> do is to use a block cipher with ECB mode.
You actually have lots of options. The most popular is
to work in units of pages. You can divide the file into
pages of, for example, two kilobytes, and encrypt these
units with a better mode. To randomly access byte 2567,
you'd need to decrypt the second page, and pull out the
byte at offset (2567-2048) within the page.
If you can afford an IV for each page, you can use one
of standard chaining modes. If not, you can use a mode
that makes each ciphertext byte dependent on each byte
in the page, and the page number, and one IV for the
file. See Peter Gutmann's SFS for an example.
http://www.cs.auckland.ac.nz/~pgut001/
> - - Decrease the amount of information stored in each byte,
> for example by using the base64 encoding scheme.
>
> - - Fill up the 'free' bits in each byte with random bits
> produced by a very good random sequence generator
> (for example the one proposed in chapter 17.14 of the
> book which I mentioned).
>
> - - Encrypt the block with a normal block cipher.
Those are good ideas. I think you'd still be better off
working in units larger than one typical cipher block.
--Bryan
------------------------------
From: Gramps <[EMAIL PROTECTED]>
Subject: Meet in the middle attack?
Date: Tue, 22 Dec 1998 03:08:21 -1000
What is a meet in the middle attack? I have books on crypto, but they do
not define that attack. I can guess what it is from the name, but my
guesses often are wrong.
------------------------------
From: <[EMAIL PROTECTED]>
Subject: Re: On living with the 56-bit key length restriction
Date: Tue, 22 Dec 1998 12:13:01 +0100
On Mon, 21 Dec 1998, Mok-Kong Shen wrote:
> [EMAIL PROTECTED] wrote:
> > ...
> > Most encryptions are done with software packages and with users that want
> > to use one single software, want it use once and type their password at
> > most once. When doing superencipherment in such a software it won't be
> > exportable.
> >
> > Relatively few users are willing to use the same or different programs
> > multiply to encrypt a message or a file. In this case superencipherment is
> > possible, but it won't become a standard.
>
> The kernel problems is 'export'. If serveral algorithms get exported
> to a country (outside of the 33), then it is very trivial to get
> someone a bit familiar with software to build a combined module
> containing more than algorithm in series to allow user comfort to be
> the same as for a single algorithm. I am quite sure that 90% of people
> using computers are capable of doing this themselves.
>
The problem is not export of algorithms - nobody is able to control this,
and - much more important: There are already enough algorithms for all
purposes. This may change with the development of new computers and new
cryptographic attacks, but surely blowfish and AES will be strong
algorithms while this stupid crypto law will be gone.
The problem is software: Keep people from using strong algorithms in
commercial mailtools and other IP tools, in office programs and databases
and you are able to destroy most of the cryptographic infrastructure.
> >
> > More important: Superencipherment doesn't work if you are using software
> > to encrypt phone calls.
>
> I don't see why it works in one case and not the other. Just regard
> the superencipherment as one single module!
>
A program that does the complete job from reading from your soundcard to
sending data to the phone line doesn't allow to add a second program to
superencipher your communication.
Once superencipherment is a single module it isn't exportable.
>
> > > > > 4. Employing multiple channels.
> > > >
> > > > Can in most cases hardly be done (as well as OTPs that are allowed).
> > >
> > > Are you absolutely sure that OTP is allowed? I would rather understand
> > > OTP to be a key as long as the OTP sequence and hence one can't
> > > use OTP longer than 56 bits (or more exactly export software
> > > using OTP of that kind?).
> > >
> >
> > Even export of OTPs from the US is allowed, so I'm quite sure.
> >
> > The main reason is: OTPs are not very useful.
>
> I prefer not to go far into OTP here (I plan to initiate a thread
> related to that sometime later.) But back to the main item above,
> employing multiple channels means simply to divide a given message
> into several pieces and encrypt these (preferably with different
> keys, but still using 56-bit algorithms) and send these through
> different channels. The analyst then has the trouble of keeping track
> of the separation done. Note in particular that the pieces may be
> sent at different time points, i.e. intentionally non-synchron, so
> that the identification of those pieces that belong to one and a
> single message is a formidable one.
This doesn't work for real-time communication or in cases where it is
impossible to add communication channels.
>
>
> > > > > 6. Using code books.
> > > >
> > > > Same as 4.
> > >
> > > Note that my code book proposal is in principle the same as
> > > ASCII encoding of the Latin alphabet. It is a public encoding
> > > and by itself contains absolutely nothing secret. So I suppose it
> > > couldn't declared to be illegal. The purpose is, as I said, to make
> > > frequency analysis difficult.
> > >
> >
> > You'll have to transmit it securely, so it's about as useful as OTPs.
>
> You misunderstood my proposal. I suggested that all people agree to
> use a 'standard' code book which is 'public', similar to the telephone
> book. There is thus no problem of trasnmission of the code book at all.
> (In the article starting this thread I mentioned the Chinese telegraph
> code as illustration.) Now if for the English world one could agree
> on a not too large subset of frequently used words and give these
> fairly random numerical values, then frequency analasis based on
> single characters, bigrams, etc. will be barely feasible (for
> messages that use the said vocabulary subset). Hence the strength of
> all kinds of encryption algorithms will profit from the existence of
> such a standard code book. The practical problem is, of course, to
> design such a code book that most people would agree to use as a
> standard. But perhaps one could just somehow make a start of such
> a project.
Why not simply compress data?
>
> M. K. Shen
>
>
Andreas Enterrottacher
[EMAIL PROTECTED]
[EMAIL PROTECTED]
------------------------------
** 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
******************************
