Cryptography-Digest Digest #7, Volume #9 Sat, 30 Jan 99 17:13:04 EST
Contents:
Re: Shattered Dreams (rosi)
Re: Idea for plaintext steganography ("Michael A. Greenly")
Re: Fialka Punch Card Speculation
Re: Washington, a DES based cipher. (Scott Fluhrer)
Re: Related Issues (part 1) (Katia Hayati)
Re: Japanese Purple encryption (Wipunxit Wiechcheu)
Re: Metaphysics Of Randomness ("Trevor Jackson, III")
Re: Random numbers generator and Pentium III ("Trevor Jackson, III")
Re: Random numbers from a sound card? ("Trevor Jackson, III")
Re: Related Issues (part 1) (Michael Hovdan)
Re: Idea for plaintext steganography (Paul Schlyter)
Re: Foiling 56-bit export limitations: example with 70-bit DES
([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: rosi <[EMAIL PROTECTED]>
Crossposted-To: sci.math,comp.theory
Subject: Re: Shattered Dreams
Date: Sat, 30 Jan 1999 10:03:48 -0800
Matt wrote:
> I have not claimed that P != NP. I do not know whether P ?= NP.
Sorry, I misread you. Apologies.
>
> > I NEVER say it is the only way. I say it is a _consistent_ way.
>
> "Consistent" isn't what's important. "P" has an accepted meaning in
> complexity theory. You are not using that accepted meaning.
I can but why must I?
"Consistent" is what mathematics is all about!
So you mean you can have things inconsistent but as long as they
are 'accepted'?
I guess the fire ball flung around the earth is still 'acceptedly'
circling the earth.
This is not an insult to science but a compliment.
Adored through quiescence.
Come on, science community. Come on!
------------------------------
From: "Michael A. Greenly" <[EMAIL PROTECTED]>
Subject: Re: Idea for plaintext steganography
Date: Sat, 30 Jan 1999 12:22:11 -0600
How any platform treats text without line breaks is obviously
software dependent, but you have to keep in mind that this approach
doesn't only apply to raw text files. It could be done with fully
justified printed documents, which are then later scanned and ocred to
recover the hidden message. The system would even work across poor fax
transmissions.
Paul Schlyter wrote in message <78vftb$eb2$[EMAIL PROTECTED]>...
>In article <[EMAIL PROTECTED]>,
>wtshaw <[EMAIL PROTECTED]> wrote:
>>In article <_Cvs2.1982$[EMAIL PROTECTED]>, "Michael A. Greenly"
>><[EMAIL PROTECTED]> wrote:
>>
>>> Another idea would be to use the number of characters per line.
Even
>>> parity is a bit set odd parity is a bit clear. This has the
advantage
>>> that it could be applied to existing text. Although there is quite
a
>>> bit of expansion.
>>
>>Macs almost never include line feeds, etc., since wordwrap is
standard.
>>The only time you will see CR's is when a list is made of short length
>>strings, or between paragraphs.
>
>Then what about source files in some computer language? These
>get quite unreadable if line breaks are removed.
>
>> Being able to handle long strings is an
>>advantage, in fact, the compiler will see ones far beyond a fixed
length
>>that would be normally specified as a limit, 256 or 512 characters.
It
>>will read from a file a single string as long as the usual buffer will
>>allow, perhaps many thousands of characters without a CR.
>
>Will the MAC handle one single line containing several million
>characters? Epsilon (an emacs clone running on PC's and on UNIX)
>handles that well.
>
>
>--
>----------------------------------------------------------------
>Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
>Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
>e-mail: [EMAIL PROTECTED] [EMAIL PROTECTED] [EMAIL PROTECTED]
>WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: Fialka Punch Card Speculation
Date: 30 Jan 99 18:25:24 GMT
Frode Weierud ([EMAIL PROTECTED]) wrote:
: [EMAIL PROTECTED] () writes:
: >The Fialka is claimed to be a 10-rotor Enigma, with a punched card
: >performing the function of the plugboard.
: >It occurs to me that, if the punched card is used to open connections in a
: >crossbar patch panel, as only one hole out of 30 is punched of those used,
: >it should not be necessary to use combinations difficult to produce on a
: >conventional keypunch machine.
: >After some thought, the following possible arrangement suggested itself to
: >me.
: >Up to 26 characters can be sent to their destinations by using 3 columns
: >for each one, the first column having a punch in any of the twelve hole
: >positions, and the remaining two using only positions 1 through 9.
: I am not able to follow your thoughts here. The Fialka rotors have 30
: contact points and not 26, as it is made for the Russian alphabet. Therefore
: the punched card "plugboard" must be seen as a 30x30 matrix. If you look at
: this you will discover that this will give you non-reciprocal connections
: much like those given by the Enigma Uhr.
Yes, you are correct. That I realized. The number 26 comes from dividing
80 by 3.
My speculation concerns how to map a 30 x 30 crossbar matrix to the
standard 80-column card. Each of the 80 columns contains 12 holes, so
three columns have 36 holes. If we use 30 holes from three columns, we
have six holes left. If they are allocated to the 12, 11, and 0 punches of
two columns, they can be punched independently of a single punch in the 1
to 9 rows, forming the code for a letter.
The idea is that a key card for the Fialka, with a suitable wiring of the
crossbar matrix, can be punched on conventional card equipment. The
diagram on my web page shows an arrangement that is simpler to draw, where
instead of the three columns for one input being together, they are
separated into three groups: and I wire 25, rather than 26, of the wires
in the "long" fashion using digit punches, with the other five using only
zone punches, leaving five columns on the card unused.
http://members.xoom.com/quadibloc/ro020404.htm
is the location. (For deciphering, the three diodes are reversed in their
action: the easiest way to do that is simply to reverse the DC polarity of
the signal from the keyboard to the printer; I will be adding that detail
to the diagram soon.)
John Savard
------------------------------
From: Scott Fluhrer <[EMAIL PROTECTED]>
Subject: Re: Washington, a DES based cipher.
Date: Sat, 30 Jan 1999 18:35:59 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (wtshaw) wrote:
>Plaintext: 192 bits, 3x64, commonly used in DES. This could be from
>binary, but it would be best done from base 64 character set which could
>be optionally subsituted as an additional key. For text, pick upper and
>lower case for 52 characters, and assign the remaining 12 characters to
>formatting and common punctuation. Don't try to make the bits directly
>from ASCII, as it lessens security.
>
>Optional substitution Key: mentioned above, 64! = 296 bits
>
>Selection Key: 6! possible combinations of ABCDEF seems trivial, but this
>is an important key, but there only a few usable permutations.
>
>DES Keys: One or Three for this cipher, a true 3DES, no interaction for 3
>keys if used.
>
>Mechanism of Encryption: Taking the plaintext 6 bits at a time, begin
>building three strings of 64 bit each. A Selection Key of AFCEFB would
>mean that bits A and F are assigned to the first string, C and E to the
>second, and F and B to the third. What do you get after putting in 192
>bits, from 64 characters, base 64? Simple, three 64 bit blocks. Apply
>either a single DES key to all three blocks, or three different DES keys
>in rotation. Build ciphertext by getting 64 bits from each DES
>encryption, 64+64+64=192. If you desire output in base 64, you get 64, or
>21 1/3 from each DES block.
Might I point out a really obvious choosen-plaintext attack: choose a
random plaintext, and that same plaintext with one bit flipped. If I
understand your scheme right, the inputs (and hence the outputs) of 2
of the 3 DES blocks will be the same, and hence all their output bits
will be the same. So, you know that any bits that change on the output
end go through the same DES block as that particular input bit. Iterate
a couple hundred times, and you can build a map of input bits to output
bits.
Once you have done that, the problem reduces to DES, possibly with three
different keys. Go steal the EFF machine (:-), and break each one
individually.
>
>Rational for Design: In any one DES block, you only have a third of the
>bits necessary to go to any plaintext character, so unicity for DES does
>not apply at all. You get a trivial few bits of additional key from the
>selection key. You can use either an original DES keylength of 56 bits,
>or a true 178 bits for three. Brute force requires the analysis of 3
>blocks, with one or three different keys, since solution of a single block
>should be meaningless.
>
>Allowance for increasing strength of the cipher: To lessen the chance of
>plaintext attack in solving a single block based on known ciphertext, vary
>the selection key, but much better, use a permuted substitution key for
>input. 64!=296 bits, but that would be politically incorrect.
Permuting the input bits, rather than considering each bit in order, would
strengthen it, but the above attack still reduces it to DES with unknown
input/output permutations (and, if that is strong enough, why don't you do
just that?). Some stronger combination method would seem to be in order
--
poncho
------------------------------
From: Katia Hayati <[EMAIL PROTECTED]>
Crossposted-To: sci.math,comp.theory
Subject: Re: Related Issues (part 1)
Date: Sat, 30 Jan 1999 10:59:16 -0800
On Sat, 30 Jan 1999, rosi wrote:
> This is to try to clarify certain issues related to my post titled
> "NP=coNP Made Easier?".
>
>
> WHAT IS 'WELL-DEFINED'?
>
> In summary, to be well-defined is to be derivable in an axiomatic
> system. Given any notion, if it can be well-defined, every of its
> components can be as well. This is recursive.
>
> A function is well-defined, if it meets the 5 listed properties.
> A hypothesized
> function remains not well-defined till it is, i.e. till the
> hypothesized parts are proven. A wrong and unproven hypothesis is NOT
> (fully) well-defined.
What about true sentences that can't be derived from axioms (Godel)? Would
they not be well-defined?
--
Katia
------------------------------
From: Wipunxit Wiechcheu <[EMAIL PROTECTED]>
Subject: Re: Japanese Purple encryption
Date: Sat, 30 Jan 1999 14:05:14 -0500
Reply-To: [EMAIL PROTECTED]
A German Enigma Macine recently went up for auction in the Washington,
DC area. The starting bid was at $20,000 - no one nibbled to the best
of my knowledge.
More recently, I saw a NEMA rotor machine go at auction for $780.
M-209s also show up and sometimes get big $$$$ for some reason.
Dave Williams
Sterling, VA
= = = = = = = =
[EMAIL PROTECTED] wrote:
>
> John,
> Thanks.
> I am particularly interested in the
> Siemens & Halske Geheimschreiber. Do you know
> if any of these machines exist, and if there is
> an antique market for such machines?
> How many of them were made, also Enigma machines.
> ===========================================================
------------------------------
Date: Sat, 30 Jan 1999 14:19:43 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Metaphysics Of Randomness
R. Knauer wrote:
> On Fri, 29 Jan 1999 19:46:37 -0500, "Trevor Jackson, III"
> <[EMAIL PROTECTED]> wrote:
>
> >Well, if strings can testify to their randomness, I want to know the shortest
> >random string.
>
> Which one? There are two shortest random strings: 1 and 0.
Good one! ;-)
>
>
> >Maybe we could work out a timesharing deal...
>
> OK by me - but I get the number 1, and you can have the number 0.
>
> Bob Knauer
>
> "No Freeman shall ever be debarred the use of arms. The strongest
> reason for the people to retain the right to keep and bear arms is,
> as a last resort, to protect themselves against tyranny in government."
> --Thomas Jefferson
------------------------------
Date: Sat, 30 Jan 1999 14:29:19 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Random numbers generator and Pentium III
R. Knauer wrote:
> On Fri, 29 Jan 1999 19:59:52 -0500, "Trevor Jackson, III"
> <[EMAIL PROTECTED]> wrote:
>
> >Correct. We label the "just know" information as unscientific and the result of any
> >rigorous investigation, major or minor, as scientific. The reason we apply these
> >lables is that the "just know" information is not objectively verifiable or
> >repeatable. The purpose of a scientific investigation is to render the reslts
> >objectively verifiable and/or repeatable.
>
> There is another element to scientific investigation, and that is to
> find a reason for why something happens. The ability to reduce a
> seemingly random process algorithmically is at the heart of finding
> reasons for its occurance.
No. Good science can be performed without reference to "why?" The predictive power of
scientific theories may convince us that we can answer the "why?" question, but it is
not
part of the process of science nor the result. It is often the motivation for people
performing science, but this is indistinguishable from other religious beliefs.
>
>
> In this example here, it is not enough to discover a test to decide on
> poison or not. It is required that a reason be found for why some
> mushrooms are poisonous and some are not.
>
> >Sure it's valid. I'd eat mushrooms on the advice of an experienced cook. But it is
> >not scientific.
>
> You wouldl not eat the mushrooms if the cook couldl not give a valid
> reason for why he claims that they are not poisonous. If he does not
> have a reason, then he is just guessing - and this could be your
> unlucky day.
His reason might be "i recognize the difference between good and bad mshrooms. If he
cannot transfer that recognition procedure to someone else it is not scientific, but it
is valid. If he can transfer that information to someone else, it is certainly
scientific as well as valid.
>
>
> If someone handed you a revolver with only one cartridge in it, and he
> told you it was perfectly safe to put it to your head and pull the
> trigger, wouldn't you want to know his reason for saying it was
> perfectly safe? If he told you he knew it was perfectly safe because
> he can see the bullet from the front of the cylinder and it is not in
> the firing position, you would accept that as proof that the gun was
> safe. But if he did not offer a valid reason, you would not accept his
> claim of perfect safety - at least not scienfically.
No, you need to pick another example. I've got some experience as a firearms trainer,
and the rules of safe handling indicate that it is not safe to point one at your head
no
matter what anyone else says. There is no scientific method by which one can prove it
to
be a safe procedure.
"Murphy uber alles" makes any sane person humble.
>
>
> Bob Knauer
>
> "No Freeman shall ever be debarred the use of arms. The strongest
> reason for the people to retain the right to keep and bear arms is,
> as a last resort, to protect themselves against tyranny in government."
> --Thomas Jefferson
------------------------------
Date: Sat, 30 Jan 1999 14:31:17 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Random numbers from a sound card?
R. Knauer wrote:
> On Fri, 29 Jan 1999 08:38:00 -0700, "Tony T. Warnock"
> <[EMAIL PROTECTED]> wrote:
>
> >Champernowne's number is the simplest example:
> >1,10,11,100,101,110,111,...=11011100101110111.... It is easy to prove that
> >all k-bit patterns have the proper frequency. This is all that is needed
> >for normality. (The concept of normality was introduced by Borel about
> >1909.) The digits of a normal number satisfy the strong law of large
> >numbers, that is, 1/2 ones, 1/2 zeros, 1/4 00's, 1/4 01's, 1/4 10's, 1/4
> >11's, ..., 1/1024 1101101101's, etc.
>
> >The problem is that the strong law of large numbers is not very strong. In
> >Champernowne's number, the excess of ones over zeros grows as N/log(N) for
> >N bits. The ratio goes like 1/2+1/log(N), really slow. The dispersion is
> >also not correct. The law of the iterated logarithm fails for all these
> >sequences.
>
> In re-reading this I spotted something I do not understand. You state
> that for the Champernowne number "all k-bit patterns have the proper
> frequency". I assume that is true for k = 1, one of the possible
> values for k.
>
> Then you say that in Champernowne's number there is an "excess of ones
> over zeros". How can that be if "all k-bit patterns have the proper
> frequency"? The "proper frequency" for k = 1 as described by you: "The
> digits of a normal number satisfy the strong law of large numbers,
> that is, 1/2 ones, 1/2 zeros".
>
> How come you state that Champernowne's number has an "excess of ones
> over zeros"?
Because all the leading zeros are suppressed.
>
>
> Bob Knauer
>
> "No Freeman shall ever be debarred the use of arms. The strongest
> reason for the people to retain the right to keep and bear arms is,
> as a last resort, to protect themselves against tyranny in government."
> --Thomas Jefferson
------------------------------
From: Michael Hovdan <[EMAIL PROTECTED]>
Crossposted-To: sci.math,comp.theory
Subject: Re: Related Issues (part 1)
Date: Sat, 30 Jan 1999 14:32:44 +0100
Katia Hayati wrote:
> On Sat, 30 Jan 1999, rosi wrote:
>
> > This is to try to clarify certain issues related to my post titled
> > "NP=coNP Made Easier?".
> >
> >
> > WHAT IS 'WELL-DEFINED'?
> >
> > In summary, to be well-defined is to be derivable in an axiomatic
> > system. Given any notion, if it can be well-defined, every of its
> > components can be as well. This is recursive.
> >
> > A function is well-defined, if it meets the 5 listed properties.
> > A hypothesized
> > function remains not well-defined till it is, i.e. till the
> > hypothesized parts are proven. A wrong and unproven hypothesis is NOT
> > (fully) well-defined.
>
> What about true sentences that can't be derived from axioms (Godel)? Would
> they not be well-defined?
>
> --
> Katia
How do you know that a sentence is true if you can't prove it from axioms? You
postulate it as an axiom in an extended (or perhaps more constrained?) theory,
right? To me that's being well-defined enough.
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: Idea for plaintext steganography
Date: 30 Jan 1999 18:35:39 +0100
In article <[EMAIL PROTECTED]>,
wtshaw <[EMAIL PROTECTED]> wrote:
>In article <_Cvs2.1982$[EMAIL PROTECTED]>, "Michael A. Greenly"
><[EMAIL PROTECTED]> wrote:
>
>> Another idea would be to use the number of characters per line. Even
>> parity is a bit set odd parity is a bit clear. This has the advantage
>> that it could be applied to existing text. Although there is quite a
>> bit of expansion.
>
>Macs almost never include line feeds, etc., since wordwrap is standard.
>The only time you will see CR's is when a list is made of short length
>strings, or between paragraphs.
Then what about source files in some computer language? These
get quite unreadable if line breaks are removed.
> Being able to handle long strings is an
>advantage, in fact, the compiler will see ones far beyond a fixed length
>that would be normally specified as a limit, 256 or 512 characters. It
>will read from a file a single string as long as the usual buffer will
>allow, perhaps many thousands of characters without a CR.
Will the MAC handle one single line containing several million
characters? Epsilon (an emacs clone running on PC's and on UNIX)
handles that well.
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: [EMAIL PROTECTED] [EMAIL PROTECTED] [EMAIL PROTECTED]
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Foiling 56-bit export limitations: example with 70-bit DES
Date: Thu, 28 Jan 1999 23:59:53 GMT
In article <78q7n5$ip0$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> In article <78pnga$3om$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] wrote:
> > In article <[EMAIL PROTECTED]>,
> > "Peter K. Boucher" <[EMAIL PROTECTED]> wrote:
> [snip]
> > > A well-known stream-cipher with variable-size keys might work as well
> > > (or better, for flexibility's sake) for your notion of M-DES.
> >
> > No, it won't ... as you say below ;-) Besides, I have the impression you did
> > not have time yet to actually read the paper, so you ignored the other
> > security features --- such as M key collision.
First, let me correct a mistake on my previous reply to Patrick Juola on this
same thread. If we take the average time the EFF DES-cracker needs to break a
56-bit key (for 50% search) to be 40 hours -- then, the average time the
DES-cracker would need to break the export-free M-DES with M =14 is 75 years.
>
> I did read your paper, and I think that if you run the stream cipher on the
> DES ciphertext, it is as secure as your method, as long as the stream cipher
> behaves well with short keys.
It is possible that you have mistyped before, as I understood you were
proposing to use the stream cipher on the *plaintext* -- please read what you
wrote:
| You pre-encrypt the entire message with the
| stream cipher, then encrypt with DES.
Was that what you meant or was it just a confusion? That is also why I
remarked on you not reading the paper, since in the paper I specifically
mention XOR�ng the DES ciphertext but never the plaintext.
Further, it is of course clear that XORing the ciphertext is ONE alternative
-- the method just calls for encrypting each DES ciphertext block.
Now, going back to your text *now*, can you please qualify what you mean by
"run the stream cipher on the DES ciphertext"? Is it just for each 8-byte
block? If it is just for 8 bytes then I can't see the word "run" being
well-used there. Or, do you envision it for all blocks at once? Or for some
blocks at once? Can you please qualify?
>
> > > For
> > > example, generate M bits randomly, use these as, hypothetically
> > > speaking, an RC4 key. You pre-encrypt the entire message with the
> > > stream cipher, then encrypt with DES. Your recipient (and any
> > > attackers) must brute-force the M-bit stream-cipher key.
> >
> > This is well-known, with well-known problems. For example, the one you cite
> > below. Further, the probability of repeating the M key for the same text
> > (message headers, for example) is not zero and increases with time, for all
> > messages -- however, pratically null in the M-DES scheme because the 64-bit
> > ciphertext itself is random and that is what is XOR-ed with the M bit key
...
> > ;-)
>
> Grabbing one of 2^M published 64-bit blocks and XORing it with the DES
> ciphertext is not more random than post-encrypting the ciphertext with a
> well-behaved M-bit sttream-cipher algorithm,
I think that is where I may have been unclear in my paper -- since you
apparently missed out on one of the core issues. It does not have to be more
random than a "well-behaved M-bit sttream-cipher algorithm". In fact, as I
cite in the paper, it can be just the following arithmetic sequence:
1 2 3 4 5 6 7 ... 2^M
The sequence of 2^M numbers can be *very* predictable. No problem and will not
reduce security by a yod.
>and may be less secure than
> post-encrypting with a good M-bit block cipher.
No, it is not less secure. See above.
> All three approaches,
> however, have the weakness that you must include a known plaintext block (or
> send only English text, or printable data), if you want to be sure that Alice
> can successfully brute-force Bob's post-encryption step.
Not the scheme I explained in the paper -- but see also [Note-2] in the
paper. If you send only random data then the effective key-length is already
120-bits, the cipher is even theoretically secure against brute-force
attacks, and you may set M = 0. However, if you send private-keys, then even
though they are pretty random you can't set M = 0. This is all in [Note-2] in
the paper -- the address is http://www.mcg.org.br/unicity.htm -- perhaps you
read the old .txt version? That would explain some of the discrepancies.
>
> > >
> > > One problem with this approach is that you must include known-plaintext
> > > in your protocol, if your recipient wants to be sure he has correctly
> > > guessed the M-bit "whitener."
> >
> > Which problem is just absent in the M-DES scheme, no? Perhaps, on purpose
'-)
>
> I don't understand how you can say it's not a problem with your scheme.
Please read above. Perhaps, the best way to see it is that the choice of M
versus thge effective key-length is a decision problem that depends on
plaintext statistics. Some extremes are:
| MESSAGE M effective key-length
|
| English text --> 14 70
| random text --> 0 120
|
OK?
>
> > And, which considerably weakens your suggestion -- perhaps too much to be
> > useful and that is why this scheme is not used, though already discussed in
> > the literature. Look for "cascadng ciphers".
>
> Choosing one of 2^M 64-bit blocks and XORing it with each 64-bit block of
> message
Not of message -- of ciphertext. Never of message.
>
>is nothing more than a really weak M-bit stream cipher. I don't
> understand why using a better stream cipher wouldn't be better.
>
Because you can't get more random than random. The ciphertext has entropy 8
bit/byte as a function of the plaintext, for a fixed 56-bit key.
To summarize the questions you posed, I believe they mostly trace to the point
that you did not see that I was specifically XORing each DES ciphertext block,
and not the plaintext in any way.
Cheers,
Ed Gerck
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
** 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
******************************
