Cryptography-Digest Digest #534, Volume #14       Wed, 6 Jun 01 10:13:01 EDT

Contents:
  Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tim Tyler)
  Re: PRP => PRF (TRUNCATE) (Nicol So)
  Re: PRP => PRF (TRUNCATE) (Nicol So)
  Re: function notation (injection, bijection, etc..) one last time 
([EMAIL PROTECTED])
  Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tim Tyler)
  Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tim Tyler)
  Re: Def'n of bijection (Mok-Kong Shen)
  Re: Best, Strongest Algorithm (gone from any reasonable topic) 
([EMAIL PROTECTED])
  Re: Best, Strongest Algorithm (gone from any reasonable topic) (SCOTT19U.ZIP_GUY)
  Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tim Tyler)
  Re: Best, Strongest Algorithm (gone from any reasonable topic) (Mok-Kong Shen)
  Re: Welcoming another Anti-Evidence Eliminator stooge to USENET  (P.    (John Myre)
  Re: Are RS codes a type of PRF? ("Niels Ferguson")

----------------------------------------------------------------------------

From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Reply-To: [EMAIL PROTECTED]
Date: Wed, 6 Jun 2001 12:32:18 GMT

Tom St Denis <[EMAIL PROTECTED]> wrote:
: "SCOTT19U.ZIP_GUY" <[EMAIL PROTECTED]> wrote in message
:> [EMAIL PROTECTED] (Tom St Denis) wrote in
:> >"SCOTT19U.ZIP_GUY" <[EMAIL PROTECTED]> wrote in message

:>   Tell what little get a third party to encrypt using your ctr
:> mod a one cipher text output file. I will guess the input. I may
:> be wrong. Then you get to guess the input to a one byte output
:> file encrypted with BICOM. If you miss I guess again. And we
:> keep doing this till one gets it right. I am willing to put
:> a thousand bucks on this. On second thought you go first.
:> Do you feel secure enough to really bet. I doubt it.

: As long as all messages are uniformly probable you win. [...]

: It's still uniformly distributed... so again I win.

So, would you like to take that bet?  Or not?
-- 
__________
 |im |yler  [EMAIL PROTECTED]  Home page: http://alife.co.uk/tim/

------------------------------

From: Nicol So <[EMAIL PROTECTED]>
Subject: Re: PRP => PRF (TRUNCATE)
Date: Wed, 06 Jun 2001 08:48:12 -0400
Reply-To: see.signature

Gregory G Rose wrote:
> 
> A PRP (by definition) produces every output value
> in its range once, and only once, if you enumerate
> the possible inputs. Now ignore for a moment that
> a PRF need not have a restricted domain, and
> assume the same set of 2^N inputs (N-bit inputs
> and outputs). Then *on average* each output
> appears once. But if the PRF is for real,
> approximately 1/e of the outputs won't appear at
> all, and some will appear multiple times. (If I
> recall correctly, the number of occurrences of a
> particular value is poisson distributed, but don't
> hold me to that...)
> 
> This difference still applies as you truncate the
> output of a PRP. For example, take the silly case
> where you just drop one bit. Now each output value
> appears exactly twice for a PRP, and on average
> twice for a PRF, but sometimes *more* than twice.
> As soon as you notice a value appear three times,
> you know that it was a truncated PRF. Conversely,
> based on the expected distribution of outputs,
> when you have enough inputs and have *not* seen a
> distribution anomaly, you know you were truncating
> a PRP, not a PRF.

What you said is true, but it doesn't mean that you can efficiently tell
whether a truncated PRF is a truncated PRP. If that were possible, you
could turn it into an efficient test for telling whether a PRF is a PRP. 

As you scale up the scheme, it will be more and more difficult to detect
the statistical anomaly caused by collisions in a non-PRF PRP.
Asymptotically, no efficient computer can tell whether a PRF is a PRP
significantly better than blind guessing.

-- 
Nicol So, CISSP // paranoid 'at' engineer 'dot' com
Disclaimer: Views expressed here are casual comments and should
not be relied upon as the basis for decisions of consequence.

------------------------------

From: Nicol So <[EMAIL PROTECTED]>
Subject: Re: PRP => PRF (TRUNCATE)
Date: Wed, 06 Jun 2001 08:51:58 -0400
Reply-To: see.signature

Nicol So wrote:
> 
> What you said is true, but it doesn't mean that you can efficiently tell
> whether a truncated PRF is a truncated PRP. If that were possible, you
> could turn it into an efficient test for telling whether a PRF is a PRP.
> 
> As you scale up the scheme, it will be more and more difficult to detect
> the statistical anomaly caused by collisions in a non-PRF PRP.
                                                    ^^^^^^^^^^^

Typo. What I meant was a PRF which is not a permutation.

> Asymptotically, no efficient computer can tell whether a PRF is a PRP
> significantly better than blind guessing.
> 
> --
> Nicol So, CISSP // paranoid 'at' engineer 'dot' com
> Disclaimer: Views expressed here are casual comments and should
> not be relied upon as the basis for decisions of consequence.

-- 
Nicol So, CISSP // paranoid 'at' engineer 'dot' com
Disclaimer: Views expressed here are casual comments and should
not be relied upon as the basis for decisions of consequence.

------------------------------

Subject: Re: function notation (injection, bijection, etc..) one last time
From: [EMAIL PROTECTED]
Date: 06 Jun 2001 09:15:14 -0400

"Tom St Denis" <[EMAIL PROTECTED]> writes:
> <[EMAIL PROTECTED]> wrote:
>>
>> Tom: I don't mind answering questions on usenet, and neither do others,
>> but at this point it really wouldn't hurt to pick up a math text. This
>> is important notation, and the definitions are quite standard. It's
>> not a winning plan to keep avoiding rigorous language.
> 
> No offense but the same could be said for half of you.  This is the third
> or so time I asked and each time I get conflicting answers.

I didn't notice too many conflicting answers, though some of the posters
simply didn't know what they were talking about.

> I shall read up a bit if I can (I don't even know if my texts explain
> thoe terms).

No offense, but these are the first terms a person *ever* learns when
studying about functions. Their definitions are *not* subject to debate,
and they are almost always stated in exactly the same way. For the last
time (please print and memorize):

1. Function: given sets A and B, a function is a subset of AxB such that
   the following two statements hold: (1) if (a1,b1) and (a2,b2) are
   members of the function, and a1=a2, then b1=b2. I.e., the function is
   ``single valued''; (2) if a belongs to A, then there exists some b
   in B such that (a,b) belongs to the function. Whenever (a,b) belongs
   to the function, we say that f(a)=b, or f:a->b.

   a. Domain: In the above definition, A is the domain of f.

   b. Codomain: In the above definition, B is the codomain of f.

   c. Range: In the above definition, the range of f is the set
      {b in B such that f(a)=b for some a in A}.

2. Injective: f:A->B is injective if and only if the following holds:
   Whenever f(a1)=f(a2)=b, it is true that a1=a2. An injective function
   is called a ``one-to-one function''.

3. Surjective: f:A->B is surjective if, for *every* b in B, there exists
   some a in A such that f(a)=b. There may be several such members of
   A. We call surjective functions ``onto'' functions. Equivalently,
   f is surjective if and only if the range of f is equal to the entire
   codomain.

4. Bijective: a function is bijective if it is both injective and
   surjective. I.e., if it is ``both one-to-one and onto''.



Now note that several results follow from bijectivity. If A and B are
sets, with a bijective function f:A->B, then:

* A and B have the same cardinality. This is ALWAYS true, whether |A| is
  finite or infinite.

* _IF_ |A| is finite, then bijectivity of f is equivalent to the statement
  that f is one-to-one and |B| equals |A|.

* _IF_ |A| is finite, then bijectivity of f is also equivalent to saying
  that f is surjective and |B| equals |A|.

* _IF_ A has infinite cardinality, then there exist injective maps
  from A to itself which are not surjective. In other words, infinite
  sets have proper subsets with the same cardinality. In other words,
  the two preceding statements fail if A has infinite cardinality.

* Every function is surjective onto its range, by definition of ``range''.

* Using definition #1 above, we see that the ``injectivity'' property is
  ``dual'' to single-valuedness, and the ``surjectivity'' property is
  ``dual'' to the property of being defined for the entire domain. It
  follows immediately that when a function is bijective, it induces a new
  function by swapping A and B in the original definition. That function
  is called the ``inverse function''. If injectivity or surjectivity fails,
  then we might speak of an ``inverse'', but the inverse is not in fact a
  function. (Note, I believe that ``dual'' here really means ``dual'' in
  a category-theoretic sense, but it's been too long; I'd have to double
  check that. Thus the quotes.)

* By the second-to-last remark, a function f which is injective but not
  surjective (i.e., it is ``into'' and not ``onto''), is in fact a
  bijection onto its range, and therefore induces an ``inverse function''
  whose domain is restricted to the range of f.

HTH,
Len.

-- 
> UTC is THE civilian time scale

Really? Arizona switched to UTC? Are you enjoying the 2 a.m. sunsets?
                                        -- Dan Bernstein

------------------------------

From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Reply-To: [EMAIL PROTECTED]
Date: Wed, 6 Jun 2001 13:08:52 GMT

Tim Tyler <[EMAIL PROTECTED]> wrote:
: JPeschel <[EMAIL PROTECTED]> wrote:
: : Tim Tyler [EMAIL PROTECTED] writes, in part:
: :>JPeschel <[EMAIL PROTECTED]> wrote:
: :>: Tim Tyler [EMAIL PROTECTED] writes, in part:

: :>: I don't follow this. It sounds as if you are re-defining an OTP.
: :>
: :>What don't you follow about it?
: :>
: :>I'm talking about a system involving a one-time random key stream, XORing
: :>it with the plaintext, and producing a cyphertext the same length as
: :>the plaintext.

: : That's an OTP and its secrecy is perfect.

: Not according to the definition of perfect secrecy.

Sometimes you hear that an OTP has perfect secrecy - but if you look at
the proof, you will normally find that it deals with the case where
all the possible plaintexts have the same length.

This is not usually a very realistic assumption in practice - and is
not the system that most people think of if you refer to an "OTP".

The commonly used system does /not/ have perfect secrecy - even if we
assume a perfectly random shared secret is available - because it fails
to conceal the length of the message.
-- 
__________
 |im |yler  [EMAIL PROTECTED]  Home page: http://alife.co.uk/tim/

------------------------------

From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Reply-To: [EMAIL PROTECTED]
Date: Wed, 6 Jun 2001 13:12:48 GMT

Mark Wooding <[EMAIL PROTECTED]> wrote:
: Tim Tyler <[EMAIL PROTECTED]> wrote:

:> No.  You are talking about an unknown 1-byte cyphertext under a
:> *known*  key.

: No.  That wasn't my error.  If k is known, there is only one possible
: plaintext!

OK, sorry.  Frankly, I didn't bother to wade through your mathematics - I
just saw you had things completely backwards, guessed at what seemed to be
the most probable cause given your conclusions, and told you of your mistake.
-- 
__________
 |im |yler  [EMAIL PROTECTED]  Home page: http://alife.co.uk/tim/

------------------------------

From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Def'n of bijection
Date: Wed, 06 Jun 2001 15:16:45 +0200



Tim Tyler wrote:
> 
[snip]
> I really don't know /why/ I'm finding it necessary to explain such basic
> stuff in sci.scrypt - but the entropy, H of a message m is given by
> H(m) = log2(1/p(m)) where p(m) is the probability of the message
> occurring.
> 
> Consequently - as I stated - all that is necessary for a message to
> have a very large entropy is for it to be *extremely* rare, and thus
> arise with a very low probability.

Very dumb question: If the opponent has a bunch of 
encrypted messages, some with high, others have low 
entropy, how is he going to have an idea of which is 
which? Thanks.

M. K. Shen

------------------------------

Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
From: [EMAIL PROTECTED]
Date: 06 Jun 2001 09:22:08 -0400

Tim Tyler <[EMAIL PROTECTED]> writes:
> JPeschel <[EMAIL PROTECTED]> wrote:
> 
>: That's an OTP and its secrecy is perfect.
> 
> Not according to the definition of perfect secrecy.  Perfect secrecy
> implies there's no information about the plaintext in the cyphertext.

You're confusing traffic analysis with cryptanalysis. The content of the
message is completely unknown. Cryptographically, that's perfect secrecy.
In terms of traffic analysis, an enemy will know:

1. The message was 243 bytes long.
2. It was sent on a Tuesday morning, right after U324 was torpedoed.
3. It was sent from U213 to Naval High Command.
4. It was sent on the emergency frequency, not than the usual channel.
5. The radioman's hands were clearly shaking as he keyed the message,
   and he had to resend twice.
6. Immediately afterward, the entire North-Pacific U-Boat fleet was
   sent coded messages, and they appear to be converging on U324's
   last known location.

That's a ton of information...sure! But it has nothing to do with the
content of the message from a cryptological standpoint. Yes, one wants
to defeat traffic analysis, but that is a separate concern from
cryptanalysis.

Len.

-- 
To obtain only high quality shareholders is no cinch.  Mrs.  Astor could
select her 400, but anyone can buy any stock.
                                        -- Warren Buffett, 1983

------------------------------

From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Date: 6 Jun 2001 13:23:04 GMT

[EMAIL PROTECTED] (JPeschel) wrote in 
<[EMAIL PROTECTED]>:

>>[EMAIL PROTECTED]  (SCOTT19U.ZIP_GUY) writes:
>
>
>>Actually  I am begining to think you don't know what a
>>OTP is for perfect security.  If one can limit the set
>>of messages to N bits then you use XOR with the pad
>>to create messages of all the same lengths That would be
>>N in this case. If one has many messages of different lengths
>>and you use an OTP for example to XOR with the short messages
>>and send that you have just limited the possible messages to
>>a subset of the possible messages you may wish to send.
>>Joe look it up. Ask Casmir.
>> Perfect security is a far stronger requirment where no possible
>>messages one wants to be encrypted can be eliminated. If you
>>only match the length of varible messages you have eliminated
>>the possibility of the other messages being encrypted.
>>Has Tom confused you.
>
>Nope, you two cats -- you and Tim -- appear to have added more
>constraints to what constitutes a one-time pad. If you haven't
>added more, tell me where I can look up and find your definition
>of a one-time pad -- uh,  somewhere other than Tim's and your posts. :-)
>
>Joe
>
>
>__________________________________________
>
>Joe Peschel 
>D.O.E. SysWorks                         
>http://members.aol.com/jpeschel/index.htm
>__________________________________________
>
>

  Joe I see why your having a problem. Most use the short
version of an OTP but for perfect security you need the
correct version. Since by defination no information can be
leaked about plain text. Most definations start by assuming
a given message length then stat you need a key that length
so they don't really cover the case of many messages of
varing length. Here is a typical URL that my help you get
the correct defination in your mind


http://whatis.techtarget.com/definition/0,289893,sid9_gci213673,00.html

"
one-time pad 
 
In cryptography, a one-time pad is a system in which a private key 
generated randomly is used only once to encryption a message that is then 
decrypted by the receiver using a matching one-time pad and key. Messages 
encrypted with keys based on randomness have the advantage that there is 
theoretically no way to "break the code" by analyzing a succession of 
messages. Each encryption is unique and bears no relation to the next 
encryption so that some pattern can be detected. With a one-time pad, 
however, the decrypting party must have access to the same key used to 
encrypt the message and this raises the problem of how to get the key to 
the decrypting party safely or how to keep both keys secure. One-time pads 
have sometimes been used when the both parties started out at the same 
physical location and then separated, each with knowledge of the keys in 
the one-time pad. The key used in a one-time pad is called a secret key 
because if it is revealed, the messages encrypted with it can easily be 
deciphered. One-time pads figured prominently in secret message 
transmission and espionage before and during World War II and in the Cold 
War era. On the Internet, the difficulty of securely controlling secret 
keys led to the invention of public key cryptography. 

How It Works
Typically, a one-time pad is created by generating a string of characters 
or numbers that will be at least as long as the longest message that may be 
sent. This string of values is generated in some random fashion - for 
example, by someone pulling numbered balls out of a lottery machine or by 
using a computer program with a random number generator. The values are 
written down on a pad (or any device that someone can read or use). The 
pads are given to anyone who may be likely to send or receive a message. 
Typically, a pad may be issued as a collection of keys, one for each day in 
a month, for example, with one key expiring at the end of each day or as 
soon as it has been used once.  

"

  Most people soon learn that you can't use it more than once and
I guess if you didn't really understand Shannons concept of perfect
security where no information is givin you might not of thought about
the length leaking info.Notice length is ususally that of longest
message. well it has to be or information that the longest message
was not sent is learned. Of course compression would shorten the
key needed.

  I don't know if this will actually help you since if your mind
is made up it will be hard to change. But do you agree that 
according to Shannon "perfect security" means no information about
the message is given. If you except his defination which I think
is the basis of modern crypto. Unless Wagner and comprany have
decided that is to secure and changed the defination.

  If the defination is true. Then for the set of message to be
encrypted. The key has to be as long as the longest message.
If a shorter cipher text is sent then you have learned that the
longest message was not sent. That is information about secret
message. It violates Shanons defination.



David A. Scott
-- 
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM"
        http://www.jim.com/jamesd/Kong/scott19u.zip
My website http://members.nbci.com/ecil/index.htm
My crypto code http://radiusnet.net/crypto/archive/scott/
MY Compression Page http://members.nbci.com/ecil/compress.htm
**NOTE FOR EMAIL drop the roman "five" ***
Disclaimer:I am in no way responsible for any of the statements
 made in the above text. For all I know I might be drugged or
 something..
 No I'm not paranoid. You all think I'm paranoid, don't you!


------------------------------

From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Reply-To: [EMAIL PROTECTED]
Date: Wed, 6 Jun 2001 13:19:39 GMT

Mark Wooding <[EMAIL PROTECTED]> wrote:

: Where I came unstuck was assuming that the symmetric cipher was
: noncompressing.  I now see that, given David Scott's bizarre chaining
: mode, the noncompressing assumption was invalid.  (I'm reading the
: version described in his public comment on AES.)

: It's a grotty chaining mode, by the way.  It's basically ECB with a knob
: on the end.  It retains the ECB property that equal plaintext blocks
: encrypt to equal ciphertext blocks.  There is no randomization in the
: encryption process.  This chaining mode cannot possibly give you a
: secure cipher in the real-or-random sense (or any of the related
: senses).  Doing nonrandomized compression beforehand doesn't help.

: It leaks too.  The final plaintext block given to the cipher can't be
: zero.  This isn't very interesting, but it shouldn't happen.

: I still don't see the point.  Using a well-analysed block cipher in CTR
: or CBC mode seems a much better idea.

You still seem to be talking about something different to us.

Davids comments (that you were responding to) related to Matt Timmerman's
BICOM system, not to his own work.

http://www3.sympatico.ca/mtimmerm/bicom/bicom.html

That uses Rijndael in CBC mode.

I can't comment about your analysis of David's system - since I
haven't looked at it yet, and I'm not clear what you're talking about.
-- 
__________
 |im |yler  [EMAIL PROTECTED]  Home page: http://alife.co.uk/tim/

------------------------------

From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Date: Wed, 06 Jun 2001 15:37:57 +0200



"SCOTT19U.ZIP_GUY" wrote:
> 
[snip]
>   If the defination is true. Then for the set of message to be
> encrypted. The key has to be as long as the longest message.
> If a shorter cipher text is sent then you have learned that the
> longest message was not sent. That is information about secret
> message. It violates Shanons defination.

I have a dumb question: If I have a short message to 
send and the key is longer, what should I do? Need I 
pad it to the length of the key and send that longer
stuff? Thanks.

M. K. Shen

------------------------------

From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Welcoming another Anti-Evidence Eliminator stooge to USENET  (P.   
Date: Wed, 06 Jun 2001 07:41:39 -0600

Eric Lee Green wrote:
<snip>
> You know you're in a crypto group when the group's response to a
> spammer is a long discourse on proof techniques and prime numbers :-).
<snip>

ROTFL

:) :)

Thank you -
JM

------------------------------

From: "Niels Ferguson" <[EMAIL PROTECTED]>
Subject: Re: Are RS codes a type of PRF?
Date: Wed, 6 Jun 2001 15:50:16 +0200

"Tom St Denis" <[EMAIL PROTECTED]> wrote in message
news:DidT6.39290$[EMAIL PROTECTED]...
> As far as I can tell RS codes (Reed-Solomon) are form of error correction
> codes (???) that were (as an example) used in Twofish to map 8 bytes
downto
> 4 bytes such that the distance is 5 bytes.
>

RS codes are used in error correction codes. Usually they are used to expand
the data to add redundancy which can then be used to detect and correct any
errors. In Twofish we used the same mathematical construction in reverse.
The RS matrix ensures that any change to four or fewer bytes in the input
will
never result in the same output.

> So could we make a 8-byte Feistel by appending a 4 byte key to one half to
> make the 8 bytes then compute the RS code on it?
>
> Do the remaining unfixed four bytes form a permutation of four bytes?
>
> The way I would see the cipher working is
>
> L,R = block
> L = L xor RS(R||K1)
> R = R xor RS(L||K2)
> L = L xor RS(R||K3)
>
> Of course some series of 8x8 sboxes could be used on the R/L inputs into
the
> RS to lower the DP and LP biases....

The RS matrix multiplication is linear in GF(2). This cipher is therefore
entirely linear, and provides no security at all. You need to add S-boxes or
something similar to break up the linear structure.

Yes, you could use an RS matrix to mix the key and the data, but why?
Most ciphers just use xor, addition, or something similar. Mixing the key
and the data is never the problem. Providing good diffusion and enough
non-linearity is.

Cheers!

Niels


> --
> Tom St Denis
> ---
> http://tomstdenis.home.dhs.org
>
>

--
======================================
Niels Ferguson, cryptography consultant.  email: niels at ferguson dot net.


------------------------------


** 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 by posting to sci.crypt.

End of Cryptography-Digest Digest
******************************

Reply via email to