Cryptography-Digest Digest #858, Volume #8 Thu, 7 Jan 99 06:13:05 EST
Contents:
Re: Help me with this crypto ! (wtshaw)
Re: On leaving the 56-bit key length limitation ([EMAIL PROTECTED])
Re: On the Generation of Pseudo-OTP (Mok-Kong Shen)
Re: On the Generation of Pseudo-OTP (Mok-Kong Shen)
Re: On the Generation of Pseudo-OTP (Mok-Kong Shen)
Re: Graph Isomorphism (Paul Rubin)
ANNOUNCE: PGP DH vs PGP RSA FAQ ([EMAIL PROTECTED])
Re: New Twofish Source Code Available (KloroX)
Re: M-94 Replica ("Douglas A. Gwyn")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Help me with this crypto !
Date: Thu, 07 Jan 1999 00:29:29 -0600
In article <770cs3$p0$[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
> I need some help with this crypto (or algorithm).
> I have a special box where you input some numbers and the box give you
> some numbers back.
> The first person who solves this will get a 40 dollars reward.
> I have some examples where i have input some numbers.
>
> Examples:
>
> Input Output
> -------- --------
> 11111111 28234105
> 00000000 84335240
> 00000001 74331395
> 00000002 12539925
> 00000003 09409071
> 99999999 84348439
> 88888888 15936752
> 10000000 25903915
> 12345678 59340407
>
> (if i input these numbers i always get the same output)
Can you reverse the process, use the Outputs for input and get Inputs for
output?
--
If government can make someone answer a question as they want him to, they can make
him lie, then, punish him for not telling the truth. Such an outrage constitutes
entrapment.
In Base 81: y\7RBRNBN 6*1O+aDR* QBOMR1OhE \*/XtS4+~ ;g/4,Y=Jn 6)IL;OC;H o93bR?bk\
v+/G(J=lE Ni@8L*x)I L(!\+O6;E Hu~u;Ho;R 9lX=g3x*n :Y(Yce;w~ 3l(9kS;NT YfmnPX=ya
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: On leaving the 56-bit key length limitation
Date: Thu, 07 Jan 1999 03:23:21 GMT
Ed Gerck wrote:
> Bryan Olson wrote:
> > Ed Gerck wrote:
> > > 1. First, I wish to point out that Theoretically-Secure Cryptographic
> > > Systems (hereafter TSCS) do not depend on key-length for secrecy --
> > > in their design region. In fact, Shannon already showed 50 years ago
> > > that a TSCS does not depend on key-length when one works within the
> > > system's "unicity distance".
> >
> > Staying within the unicity distance only ensures that
> > more than one possible decryption exists. A cryptanalyst
> > may still get large amounts of useful information.
>
> No, you are mistaken -- if you mean the plaintext (but, what else would you
> mean?).
I mean what I wrote. The information obtained from ciphertext
is the reduction in equivocation of the plaintext. There's no
rule requiring cryptanalysts to make no use of this information
until the equivocation drops close to zero.
> Where did you get this strange notion of unicity?
Shannon.
> You then reinforce
> my opinion that unicity needs to be revisited, understood in a broader scope
> and revaluated as a pratical tool.
I agree that we'd like to have a practical and provably secure
cryptosystem. Unicity distance is already well understood.
> My point is that key length only weakly determines
> the security of any system -- while unicity strongly defines it. Very large
> key length systems can be naively broken and very short key length systems
> may never be broken (never is never) -- all as a function of unicity.
That's much to vague. We know exactly how unicity distance
defines security - if the attacker doesn't have enough ciphertext,
there will be more than one plausible plaintext.
> > > 3. It is interesting to note that a TSCS cannot be attacked by
> > > exaustive key-search -- denying thus the very "brute-force attack"
> > > that looms over protocols under key length limitations. So, I can
> > > even safely use 56-bit DES (notwithstanding fast and cheap hardware
> > > key-searching devices) within a TSCS's design region.
> >
> > If TSCS is defined only as denying the attacker ciphertext
> > that covers the unicity distance, then the claim is false.
>
> TSCS is defined as a system which works within the "unicity distance" --
> please use it AS defined if you want to draw conclusions...
Perhaps I misunderstood. The unicity distance is a number of
symbols. For a given cipher (along with its keyspace) and
plaintext language, the unicity distance is the number of
ciphertext symbols such that there is one string for which the
conditional probability of that string being the correct
plaintext, given the ciphertext, is close to one.
Does "works within the unicity distance" mean that an adversary
can never get that many symbols? If it means something else,
then precisely what?
> > Exhaustive search may yield only a few possible plaintexts.
> > If I can narrow the message down to "Attack at dawn with
> > 3000 men" or "Attack at dawn with 3006 men", then I've
> > obtained almost all the useful intelligence.
>
> No, you cannot decipher anything meaningful -- you are confusing unicity with
> something else.
I'm using Shannon's meaning. If the two candidates above have
probabilities 0.39999 and 0.59999 respectively, then the
equivocation is _not_ close to zero (at 0.97 bits). The unicity
distance has not been reached.
If the ciphertext contains no information about the plaintext,
then the system has "perfect secrecy". Staying within the
unicity distance does not ensure perfect secrecy.
> > [...]
> > > For
> > > example, would a user feel limited if I say 56 Kbyte messages are
> > > allowed for each 56-bit session key -- with theoretically unbreakable
> > > security?
> >
> > Our user might not feel limited by what you say there, but
> > that would change after she reads the fine print. To achieve
> > what Ed suggests, he _must_ impose other restriction.
>
> How do you know? Is this a guess? Why do you say "must"?
Not a guess.
Theorem:
For any invertible cipher, call it f, with
f(56KB plaintext, 56-bit key) -> ciphertext,
there exists a non-trivial message space P such that for some
ciphertext y, there is exactly one solution for x in
f(x, k)=y with x in P
given y but not k.
Proof:
Consider some message space P' with more than 2^56 possible
messages, some 56-bit key K, and some message x in P.
Let y=f(x,K). The set
S = P intersect {f^-1(y, k) k in {0,1}^56}
has at most 2^56 elements, one of which is x. Now let P
be (P'-S)union{x}. Now x is the only possible decryption
of y that is in P, and x is not the only element of P.
Thus if we don't restrict the message space, we cannot avoid
messages that are uniquely identifiable from their ciphertext.
> > > 6. The final word on cryptographic strength is thus not to be found
> > > in enforced export controls for key length. It is to be found in our
> > > own drawing boards in terms of a system's "unicity distance" and its
> > > derived design issues, which is feasible to deal with and lies in our
> > > hands.
> >
> > Yuck, manager-speak.
>
> You may recognize, perhaps as an introduction to the concept of "unicity
> distance" as it is, that your phrase above is akin to a ciphertext for which I
> cannot decode any intelligible meaning -- hence, without any cipher you have
> just exemplified a TSCS system '-)
And Ed has exemplified that what he calls a TSCS easily reveals
messages to more astute analysts. '-)
[...]
> > > One simple
> > > suggestion is to reverse one or two random bits in each encrypted
> > > block of a TSCS (in a block's "salt window" defined for example by
> > > the key itself)
[...]
O.K, from other comments I gather the reversed bits are
reversed in the plaintext. (Some of my comments were based on
reading "encrypted block" to mean ciphertext). The key defines
where to put extra bits, and the values of these "salt bits" are
chosen at random. I assume that all the salt bits are removed
in the decryption process, so a pair of ciphertext and key has
a unique corresponding plaintext. Have I misunderstood anything
in the proposal?
The technique may make attacks more computationally expensive
(see "Randomized Encryption Techniques", Ronald L. Rivest and
Alan T. Sherman, Crypto 82), but does not increase the amount
of plaintext that we can encrypt before we expect decryption
to be unique. The amount of ciphertext the attacker needs will
increase, but the increase is limited to the expansion due to
salt field.
> > > Another suggestion is to
> > > develop TSCSs that can provide ambiguous and meaningful decryptions
> > > -- which the user's system can choose based on some trusted
> > > information provided out-of-band.
> >
> > Is the out-of-band channel private?
>
> The out-of-band channel is (for example) simply the previous msg, within
> unicity. It is out-of-band because it is an event in the past.
Do we assume the attacker has the previous ciphertext? If so,
then out of band channel is insignificant, since the attacker
can work with both messages. Unless we introduce new key - not
derived from or sent encrypted by the old one - the amount of
ciphertext an attacker has to work with is the sum of the two
messages.
> > > To close, in order to extract the full benefit from such approach to
> > > security as commented in the seven items above, I believe that one
> > > must first revisit the concept of "unicity distance" -- since it is
> > > usually regarded more as a "proof-of-concept" definition than a
> > > practical tool.
> >
> > Be careful. If the current understanding of unicity
> > distance fails to imply that the envisioned systems are
> > secure, that might well be a point in its favor.
>
> I cannot decipher your text -- I guess you have another unicity example :-)
Gee, I didn't even think it was all that subtle.
> But, in case you could not decipher mine ;-) ... let me "re-key" it:
>
> The current concept of "unicity distance" leads to wrong results and it is not
> practical. For example, Bruce Schneier (and others) say that the unicity
> distance of DES is 16 bytes of English, some say 20 bytes. However, it is not
> so. It is at most 4 bytes of English -- perhaps as low as 1 byte for some
> systems.
Ed's DES results are wrong. I'll explain in a follow up to
Ed's later post.
--Bryan
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: On the Generation of Pseudo-OTP
Date: Thu, 07 Jan 1999 11:32:31 +0100
R. Knauer wrote:
>
> On Tue, 05 Jan 1999 16:13:23 +0100, Mok-Kong Shen
> <[EMAIL PROTECTED]> wrote:
>
> >But before doing that I want to
> >recall that a pseudo-OTP can be obtained trivially from a PRNG, if
> >the sequence is not longer than the period of the PRNG and each
> >subsequence is never reused.
>
> A "pseudo-OTP" is just a stream cipher, and has nothing to do with the
> OTP cryptosystem unless the stream is generated by a TRNG. IOW, the
> term "pseudo-OTP" is an oxymoron. I discovered this myself when I made
> the same kinds of proposals here on sci.crypt a year or so ago.
I am not quite clear about your terminology point. PRNG is to TRNG
just like pseudo-OTP is to OTP, in my humble opiniobn. If a PRNG is
very good, it approximates a TRNG. The same is in the case of OTP.
Ideal perfection unfortunately has never existed in this universe.
So why not be satisfactory with some very good approximations? (What
is not unessential in the definition of pseudo-OTP and OTP is that
no part of it is ever reused.)
A side point, I was NOT claiming putting forward new ideas. See
the '(Remark: ....)' in the original post. I just wanted to call
attention to the utility of pseudo-OTP in light of the 56-bit
export restriction.
>
> All PRNG-based stream ciphers suffer from the fact that output is
> limited to the number of possible seeds. That means that if an
> intelligible message is uncovered in an attack, it must be the
> intended message.
>
> With the OTP system, all possible messages can be encrypted to give
> the same ciphertext, making it impossible for the attacker to know if
> he uncovered the intended message even if it is intelligible. That
> makes the OTP system totally unbreakable.
Almost covered above. An ideal OTP is a theoretical concept, it
does not exist in the world. (I mentioned this in the original post.)
>
> >One simple and convenient such source suggests
> >itself: natural language texts.
>
> You must not have been around when we discussed a similar method I
> proposed about a year ago on sci.crypt. I am sure I was not the first
> to do so.
Also covered above.
>
> In the system I proposed you would pre-agree on certain text sources
> that would change daily, like an online newspaper. Then you would use
> certain least significant digits of daily closing market figures
> (e.g., DJIA, S&P, etc.) as your offset into the various text streams.
>
> You would use only the least significant bits of the selected text
> which you would clean up using the methods discussed by Schneier to
> remove bias and correlation in stream ciphers. As long as you kept the
> procedure a secret you had a pad that for all effects and purposes
> looked like it was generated by a TRNG. Or so it would seem.
>
> That system I proposed was criticized on several counts. One person
> stated that the methods for removing correlation mentioned by Schneier
> does not work reliably in all cases, in particular LSB text streams.
> Another noted that an analyst could try all possible sources of
> Internet text, although that seems a bit much. Another claimed that it
> is unnecessary to go to all that trouble since modern cryptosystems
> such as IDEA with sufficiently large keys can never be broken as a
> practical matter. But that is not a valid criticism here, since you
> are looking for ways to circumvent key length restrictions.
I mentioned different techniques. For example, (4b) so to say distiles
one bit out of 32 or more bits. By an adequate combination of the
techniques it is intuitively very clear that one can approximate
a (practical) unpredictability. Of couse, one may have to pay the
price of high computing expenditure. But I have given arguments
to that in the original post. As to 'circumvent key length restriction'
please see also my response to Dr. Abend.
>
> >For one
> >needs only to record the offsets of the different streams participating
> >in the pseudo-OTP that has been arrived at by the previously sent
> >messages.
>
> You do not need to do that if the source of the text changes each day,
> such as online newspapers or mailing lists that you and your
> correspondent receive.
Non-zero offsets (somehow determined) can provide more 'variability'
and hence trouble to the analyst even in this case.
>
> >Some remarks to special cases: Some of the participating streams could
> >even be from the same text, i.e. differing only in offsets. In place of
> >natural language texts one could also use mathematical constants, e.g.
> >Pi. Further, since the sources are entirely public, these need not even
> >be stored at the user's place but downloaded as needed from some server
> >of the internet.
>
> At that time a year ago I also proposed using the "digit expansions"
> of certain transcendental constants like pi, ln(2), 2^1/2, etc., which
> can be computed (see Bailey-Borwein-Plouffe) using known algorithms.
> To confuse matters, one could combine different sequences from
> different offsets of different expansions and attempt to remove any
> possible bias and correlation by known techniques. The one redeeming
> feature of this over text streams is that the bit sequences
> transcendental constants are not periodic - or supposedly they are not
> periodic. Whether the sequences are biased or correlated is something
> I have never seen discussed.
>
> The one redeeming feature of this system is that there is no need to
> acquire text. All that is required is to keep the system a secret
> (like a key) and never reuse the same pad.
I didn't exclude mathematical constants (but to the contrary). But
there are enomously more texts than (easily computable) mathematical
constants to choose from. I think that what is important is how to
obtain bit sequences that approximates OTP from all such easily
available sources. That's why I liked the techniques I listed for
removing auto-correlations be discussed (or have the list expanded).
>
> >In the above I have made a humble attempt to sketch one possible way
> >of obtaining a pseudo-OTP. I should appreciate your opinions on that
> >and suggestions of other ways of advantageously generating such for
> >applications in the future 56-bit environment.
>
> I suspect that if such systems became widespread, the authorities
> would claim that the pad thus obtained constitute a key of length
> greater than 56 bits, and therefore is restricted.
Covered above.
>
> After all, the whole purpose for a 56 bit key is that there can only
> be 2^56 possible plaintexts and therefore any intelligible message
> over the unicity length of 8.2 ASCII characters obtained by a brute
> force attack must be the intended message. IOW there is only one
> intelligible message possible of length greater than 8.2 ASCII
> characters with a 56-bit cryptosystem.
That's why I recently proposed the paradigm 'security through
inefficiency' to render brute force infeasible.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: On the Generation of Pseudo-OTP
Date: Thu, 07 Jan 1999 11:35:46 +0100
R. Knauer wrote:
>
> On 5 Jan 1999 17:20:49 GMT, "jay" <[EMAIL PROTECTED]> wrote:
>
> >Strictly speaking, I suppose the key length would be the length of the
> >titles of the books and offsets, quite a bit larger than 56 bits.
>
> The notion of key length is that there can only be 2^k possible
> messages encrypted with a key of k bits. Therefore even the OTP system
> with a pad longer than 56 bits is a technical violation of the 56-bit
> restriction.
See my response to Dr. Abend.
> The upshot of the 56-bit restriction is that no matter how you try to
> hide your message, it will be exposed in a brute force attack since it
> is the only intelligible message possible if it is longer than the
> unicity distance (8.2 ASCII characters).
>
> Nowadays 56-bit brute force attacks are easy with the kind of
> equipment the govt has.
See my response to another of your follow-up.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: On the Generation of Pseudo-OTP
Date: Thu, 07 Jan 1999 10:52:25 +0100
Dr.Gunter Abend wrote:
>
> Mok-Kong Shen wrote:
> >
> > In light of the forthcoming 56-bit key length restriction it appears
> > valuable to re-contemplate on all available techniques in cryptology
> ...
> thereby sorting them into two classes: those obeying the 56-bit
> restriction, and others. OTP violates the bound!
I suppose you and a few others misunderstood an essential point.
The 56-bit restriction is an EXPORT restriction. That is, people
outside of the 33 countries are (legally) unable to obtain cryptos
of larger key lengths either to communicate in their own countries
(where there may be NO crypto laws whatsoever) or with people of the 33
countries (so long as there is no restriction of USE of encryption as
is in France). So the communication partners CAN use OTP or psuedo-OTP.
My point is that pseudo-OTP can be easily built, i.e. no softw
generated, then security of most civilian communication can be
(re-)achieved through that (as one of the possible ways).
> The question of the 56-bit bound then refers to the size of the seeds
> used for selecting the actual pseudo-OTP out of the common data base.
>
> If you really want to obey the 56-bit bound, this method is as weak as
> other techniques.
>
> Of course, if the data base is hidden, i.e. the appointment about the
> actual text (retrieved from e.g. the internet) is done along a secure
> channel, this method may be safe, but: A program that *allows* the
> use of an arbitrarily specified data base with an arbitrary offset as
> a pseudo-OTP violates the 56-bit bound in the same way as PGP violates
> the bound if it doesn't cut a long key down to the allowed size.
Covered above.
> The only chance I can see is the combination of several encryption
> techniques *by hand*, i.e. encrypting the plain text with one method
> and sending the intermediate text by a different 56-bit program. If
> cryptanalysis of a specific combination shows that one really has a
> 2^56x2^56 bit key space, then everybody, even the governments, should
> grasp that the crypto law is nonsense.
Superencipherment is a viable method. I mentioned this in a previous
post (also in http://www.stud.uni-muenchen.de/~mok-kong.shen/#paper17)
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: Graph Isomorphism
Date: Thu, 7 Jan 1999 09:53:51 GMT
In article <[EMAIL PROTECTED]>,
Soeren Mors <[EMAIL PROTECTED]> wrote:
>[EMAIL PROTECTED] (Alan Martin) writes:
>> Is graph isomorphism still considered to be a hard problem suitable
>> for use in cryptography?
>
>It is still considered hard.
I seem to remember that M. Sipser and S. Goldwasser had a very clever
argument (not quite a proof) that graph isomorphism is in P. I don't
remember how it went, except it was totally non-constructive (i.e.
they gave evidence that a P-time algorithm existed but this gave no
clue as to what the algorithm might be). Anyone know more about this?
It would have been from the mid or late 80's.
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: talk.politics.crypto,alt.privacy
Subject: ANNOUNCE: PGP DH vs PGP RSA FAQ
Date: Thu, 07 Jan 1999 09:58:46 GMT
Dear all,
I have now completed the PGP DH vs PGP RSA FAQ, and have posted the complete
document to comp.security.pgp.discuss / alt.security.pgp
It was my intention to also post the FAQ here for peer review, but it comes to
about 90Kb in total - and I didn't fancy getting a flaming for posting that
much off-topic material to the group.
If anyone is interested, the FAQ is also available at
http://www.hertreg.ac.uk/ss/
Any comments gratefully received,
--
Sam Simpson
Comms Analyst
-- http://www.hertreg.ac.uk/ss/ for ScramDisk hard-drive encryption &
Delphi Crypto Components. PGP Keys available at the same site.
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (KloroX)
Subject: Re: New Twofish Source Code Available
Date: Thu, 07 Jan 1999 09:38:08 GMT
Reply-To: [EMAIL PROTECTED] (this is spam bait)
>[EMAIL PROTECTED] (Bruce Schneier) wrote:
>
>>As far as I know, the Twofish source archives outside the U.S. have
>>not yet been updated to the most recent source code.
Just to know what to look for, what is the file name of the archive?
File names should not be subjected to export restrictions.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: M-94 Replica
Date: Thu, 07 Jan 1999 09:44:59 GMT
Dave Smith wrote:
> That set is confirmed in several texts and articles. Note that it is
> different from the set used on the Pampanito web site ... I think the
> Pampanito set is in error, and that the set from Friedman is correct.
If anybody really cares, last time I was in the Friedman archives at
Marshall Library, there was an M-94 that was nearly intact (one disk
may have been missing).
------------------------------
** 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
******************************
