Cryptography-Digest Digest #915, Volume #13 Fri, 16 Mar 01 11:13:01 EST
Contents:
Re: What do we mean when we say a cipher is broken? (Was Art of (William Hugh
Murray)
Re: Encrypt then HMAC or HMAC then Encrypt? (D. J. Bernstein)
Re: Noninvertible encryption ("Douglas A. Gwyn")
Re: Super strong crypto ("Douglas A. Gwyn")
Re: Super strong crypto ("Douglas A. Gwyn")
Re: An extremely difficult (possibly original) cryptogram ("Douglas A. Gwyn")
Re: What do we mean when we say a cipher is broken? (Was Art of ("Douglas A.
Gwyn")
Re: How to eliminate redondancy? ("Trevor L. Jackson, III")
Re: Schneier's cryptanalysis self-study course (Derek Bell)
Cipher Idea #1 Block Cipher 512-bit block, arbitrary keysize (long) ("Joseph
Ashwood")
Re: Digital enveloppe ("Ray")
Re: How to eliminate redondancy? ("Douglas A. Gwyn")
----------------------------------------------------------------------------
From: William Hugh Murray <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: What do we mean when we say a cipher is broken? (Was Art of
Date: Fri, 16 Mar 2001 14:16:39 GMT
Mok-Kong Shen wrote:
> John Savard wrote:
> >
> > William Hugh Murray<[EMAIL PROTECTED]> wrote:
> >
> > >I am not at all sure what you mean by "broken." Do you mean that the cost
> > >of recovering a message without benefit of the key suddenly falls to
> > >zero?
> >
> > A cipher is broken when that cost is less than infinity. Or, given the
> > existence of brute-force search for all but the OTP, when that cost
> > becomes low enough that someone actually _could_ spend the money. A
> > cipher is *not* broken when the messages sent in it actually _cannot_
> > be read.
>
> But the phrases above 'cost is less than infinity' and
> 'cost becomes low enough that someone actually could
> spend the money' don't have the same meaning and could
> eventually have the distance of heaven and earth between
> them, I am afraid. If 'broken' is reserved for use in the
> sense of the first phrase, then one badly needs another
> term for the second phrase.
>
> M. K. Shen
Thank you, sir. My point exactly. If we cannot have a single agreed upon
meaning for the word, perhaps we would be better off not using it at all.
I am reminded of Courtney's definition for integrity, i.e., "As good as we think
it is." I can use a cipher effectively if it is as good as I think it is.
Gwynn and Savard seem to suggest that the gap between my perception and
perfection is simply too big to cope with. They seem to suggest that in
encryption one knows perfection or one knows nothing. They suggest that even if
one allows for the possibility that some closed group of cryptographers somewhere
knows of an attack that one does not know about, that that possibility, no matter
how small, no matter how great the allowance, is intolerable. While I can build
a hypothetical where this is true, the amount of data that fits in such a
hypothetical is sufficiently small that I am not likely to encounter it.
I thought Gillogly's point about a "set of messages" was also important. One
assumption that I always make in the use of cryptography is that a nation state
can read any single message that it wants to read badly enough. The use of even
perfect cryptography cannot prevent that. However, the use of less than perfect
cryptography can prevent them from reading every message that they want.
Many probably thought that I was being facetious when I suggested as a definition
of "broken" that the cost of recovering a message without benefit of the key
dropped suddenly to zero. I wasn't. In fact, that is the way many read the
word. I know people who insist that the NY Times told them that DES is broken in
that sense, broken in the sense that it is unsuitable for any use. Some of them
have said it without challenge in this forum .
Even if DES is broken in the sense that the cost of decrypting a message without
benefit of the key (to some small closed population of cryptanalysts) is less
than my expectation, it is not broken in the former sense. As long as it is not
broken in that sense I can still use it effectively for some applications.
Savard and Gwynn would deny me the use of selecting applications for defining
"not broken" while choosing what may well be an empty set of applications for
defining broken.
They suggest that a cipher that does not offer forward security for fifty years
is "broken." While I might concede that there are applications for which this
may be true, I am not yet ready to concede it in the general case. While I can
hypothesize such information, except in national security applications, I can
think of hardly any real information that has a required cover time measured in
decades. (The spooks contend that they keep the names of sources secret for 75
years so that they cannot be coerced by threats to their grandchildren. In fact
they do not seem to be able to keep the names secret long enough to prevent the
spies from dying by a bullet to the head. Mr. Hannsen seems to demonstrate that
one should not both spy and "give hostages to fortune.")
I repeat my suggestion. If we cannot agree upon use of the term, let's stop
using it. Let us use instead the explicit statement of the class of
vulnerability that we are talking about, the definition of broken that we using.
William Hugh Murray
------------------------------
From: [EMAIL PROTECTED] (D. J. Bernstein)
Subject: Re: Encrypt then HMAC or HMAC then Encrypt?
Date: 16 Mar 2001 14:19:37 GMT
Paul Crowley <[EMAIL PROTECTED]> wrote:
> Interesting: how does this compare to UMAC?
Both authenticators provide 16 bytes of protection at very high speed.
For example, hash127+Rijndael takes about 800 Pentium Pro cycles to
authenticate a 64-byte packet, or 1600 Pentium Pro cycles (or 1000
Athlon cycles) to authenticate a 256-byte packet.
hash127 has a much simpler definition than UMAC, is much easier than
UMAC to implement, performs well on a broader variety of current chips
than UMAC does, can take advantage of many more chip designs than UMAC
can, and has slightly lower circuit complexity than UMAC.
Beware that the UMAC authors habitually quote performance results for a
breakable 8-byte security level. I refuse to participate in that game.
---Dan
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Noninvertible encryption
Date: Fri, 16 Mar 2001 14:26:22 GMT
"SCOTT19U.ZIP_GUY" wrote:
> [EMAIL PROTECTED] (Paul Crowley) wrote ...
> >But there's no real security issue since our ciphers are designed to
> >resist known-plaintext attack.
> I like the disclaimer "know-plaintext attack" Unfprtunatately
> its the plaintext attack that you don't know about when you use
> a method that ends up bitting you in the ass.
Do you really not know that in a "known-plaintext attack" it is
the plaintext that is known, not the attack?
> ... The closed minded belief is that compresion headers are the
> only problem and not the general structure of the output file.
> Well they are wrong.
It would be useful to explain why, because it certainly appears that
a compressed file has less structure "everywhere" except near the
beginning where not only might there be a header but also the
dictionary is being filled at a rapid rate.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Super strong crypto
Date: Fri, 16 Mar 2001 14:30:09 GMT
Mok-Kong Shen wrote:
> I think that you exaggerated a bit. In your scenario,
> the volume of new keys sent is large comparable to
> the size of the initial key, if I don't err. The 'key
> distribution key' simply means doubling the initial key.
> So the comparison is 1+n vs. 2+n, n being the total number
> of new keys.
No, I analyzed it correctly. It is the shared secret
that matters. In either approach, additional keying
material is "free".
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Super strong crypto
Date: Fri, 16 Mar 2001 14:38:16 GMT
Bryan Olson wrote:
> ... The information theoretic analysis shows that ...
There hasn't been a proper information-theoretic analysis.
The one that was posted was based on an unrealistic costing
model, namely no limit on computation.
> ... Your system bloats the ciphertext, so even if cryptanalysis
> requires more ciphertext, your mode may provide it.
No, because the "bloat" is pure entropy.
> Your paragraph above is the kind of thing I described as
> hypothesizing a weakness and conjecturing a fix. You have
> no reason to believe K is generally tractable, and no way to
> show that your scheme would make the work factor intractable.
Actually, I have plenty of reason. It's called experience.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Crossposted-To: rec.puzzles
Subject: Re: An extremely difficult (possibly original) cryptogram
Date: Fri, 16 Mar 2001 14:41:47 GMT
Henk van Voorthuijsen wrote:
> > >20650362042 may mean "basic" or "fundamental".
> I would say it's in the "c" range, right?
No, it's "general". Also, 27465680662 is "however".
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: What do we mean when we say a cipher is broken? (Was Art of
Date: Fri, 16 Mar 2001 15:00:05 GMT
William Hugh Murray wrote:
> Gwynn and Savard seem to suggest that the gap between my perception
> and perfection is simply too big to cope with. They seem to suggest
> that in encryption one knows perfection or one knows nothing. They
> suggest that even if one allows for the possibility that some closed
> group of cryptographers somewhere knows of an attack that one does
> not know about, that that possibility, no matter how small, no matter
> how great the allowance, is intolerable.
> ...
> Savard and Gwynn would deny me the use of selecting applications for
> defining "not broken" while choosing what may well be an empty set of
> applications for defining broken.
First, please spell my name right.
Second, I haven't addressed "your perception" at all nor denied you
anything; your characterization above is wrong. In a thread
concerning what "super strong crypto" might require, I addressed the
very real problem of one's ignorance of possible effective methods
of cryptanalysis and what might be done about that problem.
Certainly the appellation "super strong crypto" would not be
properly applied to a system that was being routinely read by
skilled cryptanalysts.
If you want to blindly trust some cryptosystem, you are free to
do so. But it would be to your advantage to have a reliable
estimate of the likelihood that whoever you are trying to hide
secrets from is able to access them. Or, in fewer words, that
the adversary can "break" the system.
Not talking about breaking systems doesn't block the activity.
------------------------------
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: How to eliminate redondancy?
Date: Fri, 16 Mar 2001 15:07:42 GMT
br wrote:
> It will reduce little bit a redundancy. So compression is better.
> Is there any other way other than compression.
Yes. Masking.
Given a highly redundant plaintext one can eliminate the redundancy by masking
with a good PRNG. Unfortunately this does not provide any extra strength
because the attacker can unmask just as easily as the receiver. To defeat this
requires that the key be expanded to include the PRNG seed.
------------------------------
From: Derek Bell <[EMAIL PROTECTED]>
Subject: Re: Schneier's cryptanalysis self-study course
Date: Fri, 16 Mar 2001 15:20:27 +0000
Kay Connelly wrote:
>
> I'm starting to work through Bruce Schneier's "A Self-Study Course
> in Block-Cipher Cryptanalysis"
> (http://www.counterpane.com/self-study.html).
>
> I'm looking for a couple of people who would be interested in
> working through it together... exchanging ideas and brain-storming
> before we give in and look for a published solution. If you're
> interested, let me know.
I'd be interested.
--
_________________________________________________________________________
Mr. Derek Bell, | Telephone: 00+353-1-6082288
Electronic & Electrical | Mobile: 00+353-087-6637874
Engineering Department, | Fax: 00+353-1-6772442
Printing House, | Email: [EMAIL PROTECTED]
Trinity College Dublin, | Dept: http://www.mee.tcd.ie/mobile_radio
Dublin 2, | Map: http://www.tcd.ie/Maps/tcd_central.html
Ireland. | www: http://www.maths.tcd.ie/~dbell
_________________________________________________________________________
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Cipher Idea #1 Block Cipher 512-bit block, arbitrary keysize (long)
Date: Mon, 12 Mar 2001 21:44:36 -0800
This is primarily an experiment in parrelizability, other than that it is a
curiosity cipher, not a security cipher, I do however look forward to the
slaughter of the cipher or the author as is deemed fit.. The KeySchedule can
be partially parellelized, but has portions that are inherently sequential,
this makes for a rather severe penalty for rekeying. The encryption itself
can be fully parellelized at a rate of 16 simultaneous operations. It
contains no inherent chaining. It is currently parameterized on the number
of rounds as well. It is double unbalanced Feistel network, with a 3:1 and a
1:3 phase during each of the 4 subrounds. Each subround of encryption
requires a minimal amount of math (a handful of additions and XORs).
This is a curiosity, not a security cipher. I place it in the public domain.
If the specification is unclear please tell me, I will remedy that problem.
Array Sbox[512] of OCTET
KeySchedule(Key)//Key is treated as a Big Endian integer
prepend HEX(209C) to Key
Linked List PreBox of OCTET
for(0<=iteration<512)
OCTET current = iteration MOD 256
add current to end of PreBox
end for
Make PreBox circular (PreBox should now be a circular linked list of
0......255 0 ... 255 with the head pointing at 0)
integer tempKey
for(0<=iteration<4)
tempKey = Key MOD HEX(209)
rotateRight(Key, 7 bits)
for(0<=LocalIteration<tempKey)
Iterate PreBox one location around the linked list
end for
end for
for(0<=iteration<512)
tempKey = Key MOD HEX(209)
rotateRight(Key, 7 bits)
for(0<=LocalIteration<tempKey)
Iterate PreBox one location around the linked list
end for
OCTET midBox = current PreBox location
remove current PreBox location from linked list
Sbox[iteration] = midBox
end for
//Sbox will now hold a permutation of the 512 elements in PreBox, and PreBox
will be a null list
//Specifically Sbox now has two and only two entries of each integer 0...255
inclusive in some key determined order
end KeySchedule
Encrypt(inputBlock, numRounds)//inputBlock is 512-bits arranged in OCTETs
//all addition is done modulo 8 to avoid going outside the bounds of the
array
Array block[8][8] of OCTET
for(0<=i,j<8)
block[i][j] = inputBlock[i*8+j]
end for
integer offset = 0
for(0<=round<numRounds)
for(0<=i<4)
for(0<=j<4)
//first quarter round
block[2*i+0][2*j+0] = block[2*i+0][2*j+0] XOR
Sbox(block[2*i+0][2*j+1]+offset)
block[2*i+0][2*j+0] = block[2*i+0][2*j+0] XOR
Sbox(block[2*i+1][2*j+1]+offset+7)
block[2*i+0][2*j+0] = block[2*i+0][2*j+0] XOR
Sbox(block[2*i+1][2*j+0]+offset+14)
block[2*i+0][2*j+1] = block[2*i+0][2*j+1] XOR
Sbox(block[2*i+0][2*j+0]+offset+21)
block[2*i+1][2*j+1] = block[2*i+1][2*j+1] XOR
Sbox(block[2*i+0][2*j+0]+offset+21)
block[2*i+1][2*j+0] = block[2*i+1][2*j+0] XOR
Sbox(block[2*i+0][2*j+0]+offset+21)
offset = offset + 31
end for
end for
for(0<=i<4)
for(0<=j<4)
//second quarter round
block[2*i+0][2*j+1] = block[2*i+0][2*j+1] XOR
Sbox(block[2*i+0][2*j+2]+offset)
block[2*i+0][2*j+1] = block[2*i+0][2*j+1] XOR
Sbox(block[2*i+1][2*j+2]+offset+7)
block[2*i+0][2*j+1] = block[2*i+0][2*j+1] XOR
Sbox(block[2*i+1][2*j+1]+offset+14)
block[2*i+0][2*j+2] = block[2*i+0][2*j+2] XOR
Sbox(block[2*i+0][2*j+1]+offset+21)
block[2*i+1][2*j+2] = block[2*i+1][2*j+2] XOR
Sbox(block[2*i+0][2*j+1]+offset+21)
block[2*i+1][2*j+1] = block[2*i+1][2*j+1] XOR
Sbox(block[2*i+0][2*j+1]+offset+21)
offset = offset + 31
end for
end for
for(0<=i<4)
for(0<=j<4)
//third quarter round
block[2*i+1][2*j+1] = block[2*i+1][2*j+1] XOR
Sbox(block[2*i+1][2*j+2]+offset)
block[2*i+1][2*j+1] = block[2*i+1][2*j+1] XOR
Sbox(block[2*i+2][2*j+2]+offset+7)
block[2*i+1][2*j+1] = block[2*i+1][2*j+1] XOR
Sbox(block[2*i+2][2*j+1]+offset+14)
block[2*i+1][2*j+2] = block[2*i+1][2*j+2] XOR
Sbox(block[2*i+1][2*j+1]+offset+21)
block[2*i+2][2*j+2] = block[2*i+2][2*j+2] XOR
Sbox(block[2*i+1][2*j+1]+offset+21)
block[2*i+2][2*j+1] = block[2*i+2][2*j+1] XOR
Sbox(block[2*i+1][2*j+1]+offset+21)
offset = offset + 31
end for
end for
for(0<=i<4)
for(0<=j<4)
//fourth quarter round
block[2*i+1][2*j+0] = block[2*i+1][2*j+0] XOR
Sbox(block[2*i+1][2*j+1]+offset)
block[2*i+1][2*j+0] = block[2*i+1][2*j+0] XOR
Sbox(block[2*i+2][2*j+1]+offset+7)
block[2*i+1][2*j+0] = block[2*i+1][2*j+0] XOR
Sbox(block[2*i+2][2*j+0]+offset+14)
block[2*i+1][2*j+1] = block[2*i+1][2*j+1] XOR
Sbox(block[2*i+1][2*j+0]+offset+21)
block[2*i+2][2*j+1] = block[2*i+2][2*j+1] XOR
Sbox(block[2*i+1][2*j+0]+offset+21)
block[2*i+2][2*j+0] = block[2*i+2][2*j+0] XOR
Sbox(block[2*i+1][2*j+0]+offset+21)
offset = offset + 31
end for
end for
offset = offset + 127
end for
end Encrypt
I'm not going to take up extra space with decrypt. I haven't taken a
significant amount of time to analyze it yet, however I do note that full
diffusion occurs after 8 rounds, I recommend 13 rounds. Differential
behavior is likely to be very difficult to find due to the continually
changing sboxes. Linear behavior is unlikely again because of the
continually changing sboxes.
Attacks on reduced versions:
Attacking a version with only the 3:1 (the first phase of each quarter
round) or a version with only the 1:3 (second phase of quarter round) will
have either a linear or differential probability that is much higher than
the resulting cipher.
Space requirements:
The space requirements for encryption are rather large in the current realm
of algorithms, requiring 512 Octets of per key storage, to encrypt takes
another several bytes. This is obviously not entire good, however in
hardware the requirement to only have 9 bit adders, and XORs should
compensate for the memory requirements. Specifically an SRAM cell only takes
6 transistors, roughly twice that needed for other gates. This still should
be doable at about the 10k transistor level, which would make it one of the
smaller die space cryptosystems around.
Speed analysis:
The entire encryption can be performed with only addition, XOR and table
lookup instructions, making this ideally suited to hardware. The ability to
parellelize to 16 easily also makes hardware an obvious solution. The need
for an estimated 4*13 quarter rounds could make this a slower then
visualized cipher, I feel this is compensated for by the simple fact that it
operates on 512 bits at a time, instead of 64 or 128.
The Key Schedule is another matter entirely, it is very compute intensive,
and will take a significant amount of time, and should be done in software
because the vast majority of the gates could not be realistically reused.
Under normal usage this should not be an issue because the keying
information will generally pass through a general purpose computer anyway.
In cases where software keying is not acceptable a single key schedule
generator can be used to feed a significant number of encrypt/decrypt
engines.
I await the traditional slaughter of the cipher. Just a reminder this is a
curiosity cipher, I have little expectation that it will be secure.
------------------------------
From: "Ray" <[EMAIL PROTECTED]>
Subject: Re: Digital enveloppe
Date: Fri, 16 Mar 2001 16:33:32 +0100
This is an interesting discussion. The only people I miss are the inventors
of Digital Envelope. Did somebody contact them ?
In my opinion they can achieve their goal as follows:
With symmetric encryption you always need a piece of software that does the
decryption. What if their Personal key is just a customized missing piece of
software that does the decryption only for the specified email address ? The
software without the key just encrypts, but never decrypts.
Or am I absolutely mistaken ?
Ray
"br" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> I found a site using my idea but my idea doesn't need any Pin or
> password.
> http://www.digital-envelope.com/
>
> Only the recipient can open the email.
>
> Description of the system "digital enveloppe". I just quote it
>
> Digital Envelope is a simple but efficient way to encrypt all your
> emails so that nobody else than the
> recipient of the mail is able to read what you sent.
>
> The way it works:
>
> You encrypt your message with the recipients email address as
> key. You also can define how long the
> message will be readable by specifying an expiration period.
> If you have something really secret, you
> may enter an extra PIN or pass phrase. You must inform the
> recipient about this extra PIN, because
> otherwise s/he cannot read it. Then send your message.
>
> The recipient will get the encrypted message in the Inbox of
> the mail client. In order to decrypt it, a
> personal key must be requested here. The personal key is
> protected by a customer chosen Pin or pass
> phrase and is delivered by email to the email address
> specified in the key. Then the gets activated and
> the recipient can read your mail. So easy.
>
> We provide you with all the small pieces of software you will
> need for free, so visit our download pages.
>
> Some cryptographic details:
>
> The encryption uses a 128 symmetric encryption and in
> addition a chameleon type algorithm that
> changes its behavior during the encryption. We think, its
> pretty secure. Still there are more secure
> encryption schemes available, but this one will give you a
> good level of privacy.
> ______________________________________
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: How to eliminate redondancy?
Date: Fri, 16 Mar 2001 15:51:42 GMT
"Trevor L. Jackson, III" wrote:
> Given a highly redundant plaintext one can eliminate the redundancy
> by masking with a good PRNG.
I guess at this point we ought to ask what people mean by "redundancy".
To me, that scheme doesn't reduce redundancy by more than the bits in
the PRNG parameters. It does make it more "latent", however.
------------------------------
** 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
******************************
