Re: Cryptographic Algorithm Metrics
At 10:38 PM + 1/3/2001, Peter Fairbrother wrote: >on 3/1/01 9:25 pm, Greg Rose at [EMAIL PROTECTED] wrote: > > > At Crypto a >> couple of years ago the invited lecture gave some very general results >> about unconditionally secure ciphers... unfortunately I can't remember >> exactly who gave the lecture, but I think it might have been Oded >> Goldreich... forgive me if I'm wrong. The important result, though, was >> that you need truly random input to the algorithm in an amount equal to the >> stuff being protected, or you cannot have unconditional security. > >Not so. Perfect compression with encryption works too. > How does perfect compression prevent a known plaintext attack? Arnold Reinhold PS I am also curious why Mr. Smith considers 1024-bit RSA to be "Conditionally Computationally Secure."
Re: Cryptographic Algorithm Metrics
A couple of people have taken me to task for complicating the question about One Time Pads. The purpose of my original text was just to say that yes, there are other useful and deployed algorithms out there that have unconditional security, and that it is not the case that One Time Pads are special in that sense. I have often seen the claim that "only one time pads are provably secure", and this bugs me. >Greg Rose wrote: > > > > At 11:01 PM 1/3/2001 +, someone wrote: > > >Don't you think that's a pretty good reason for singling it out? Is > > >there any additional merit in the more complex realisations? > > > > I just meant that there's a widespread assumption that the *only* > > unconditionally secure algorithm is the One Time Pad. This assumption is > > incorrect. But I don't think it is worth cluttering the list with this > > point... I shouldn't have said anything. > >Well, it may be, but that would require answering the second question in >the affirmative: do they have any additional merit? Well, I gave one example. Shamir Secret Sharing is: . unconditionally information-theoretically secure . requires truly random information to be secure . is clearly useful . is implemented in a number of publicly available packages . is not equivalent to a one-time-pad except in a degenerate case >Clearly I can obfuscate any crypto algorithm by adding other stuff to it >(e.g. Blowfish+RSA by using the first two primes above the key to >generate an RSA key) but it doesn't get us anywhere. Yes, there are an infinite number of ways to use shared random information in complicated ways, or to complicate other algorithms, but that wasn't what I was getting at. >What intrigues me is the idea that there may (or may not) be more to the >methods you describe than mere obfuscation, though I doubt there is. To further expand the stated example, the way Shamir secret sharing works is to give to n parties information such that any t (threshold) of them can reconstruct the secret. It does this by choosing AT RANDOM t-1 coefficients of a t-th degree polynomial, and using the secret data as the other coefficient. The "shares" are the values of the polynomial evaluated at independent points. When you have only t-1 data points, the interpolating polynomial is incompletely specified, and the set of possible polynomials (and therefore the set of possibilities for the secret) is as large as the underlying group. When there are t data points available, the interpolating polynomial is completely specified, and the data is uniquely revealed. See page 526 of the Handbook of Applied Cryptography for the full detail here, in particular note 12.72. I claim that this is not obfuscation, and is a non-trivial application. QED. I guess I should mention that the packages I've looked at that implement it use non-random numbers generated for example by DES, thus artificially limiting its security (for example, with two shares, one could brute-force the DES key to verify guesses for the "randomly generated" coefficients and recover the secret, even if more than two shares were otherwise needed). So it really is like the OTP in that regard -- if the numbers are truly random, it is provably perfectly secure, but if they aren't, all bets are off. >Feel free to reply to this on the list. :-) Done. regards, Greg. Greg Rose INTERNET: [EMAIL PROTECTED] Qualcomm Australia VOICE: +61-2-9817 4188 FAX: +61-2-9817 5199 Level 3, 230 Victoria Road,http://people.qualcomm.com/ggr/ Gladesville NSW 2111232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C
Re: FC: Congress weighs crypto-in-a-crime, wiretapping legislation
Finally catching up on some email... I didn't write the article; it was published in the National Review, a weekly conservative newspaper (http://www.nationalreview.com/kopel/kopel121500.shtml). I assume they do at least rudimentary fact checking, and I believe David Kopel, the author, to be a careful writer. You can find the text of the "medal of valor" legislation, which does not look like it passed during the 106th Congress, here: http://thomas.loc.gov/cgi-bin/query/z?c106:H.R.46: Of interest to the list is the crypto-in-a-crime provision: (c) AMENDMENT OF SENTENCING GUIDELINES RELATING TO USE OF ENCRYPTION- Pursuant to its authority under section 994(p) of title 28, United States Code, the United States Sentencing Commission shall amend the Federal sentencing guidelines and, if appropriate, shall promulgate guidelines or policy statements or amend existing policy statements to ensure that the guidelines provide sufficiently stringent penalties to deter and punish persons who intentionally use encryption in connection with the commission or concealment of criminal acts sentenced under the guidelines. Similar language was included in some of the "crypto liberalization" bills such as SAFE in the past. -Declan On Thu, Dec 28, 2000 at 10:00:52AM -0500, William Allen Simpson wrote: > Declan, I've looked at the floor activity for that day, and searched > the house record [Page: H12100 et seq]. I cannot find any mention of > HR.46, or "encryption", or "wiretapping". I also looked at every > reference to the word "computer", which appears frequently. > > Could your sources be more specific as to how this was passed? > > Sometimes, it's better to say "Senate" when you mean only the Senate, > and give specific names of supporters (Stevens, Hatch), rather than > tarring the whole "Congress" with bills that are going nowhere. >
Re: Cryptographic Algorithm Metrics
Peter Fairbrother <[EMAIL PROTECTED]> writes: > Not so. Perfect compression with encryption works too. Er, does it? I get a 1k message from you, perfectly compressed and then encrypted with some strong algorithm and a 128-bit key. As a godlike being unhindered by constraints of computational power, I try all 2^128 possible keys, and find due to the perfect compression that each of the 2^128 plaintexts is equally likely. From an information theoretic point of view, I'm much better off than I was before: I used to be missing 8192 bits of entropy, but now I'm only missing 128 - the space of possible messages has been vastly reduced. Put it this way, if all I want to know is whether you're asking for a ticket to the dance, I might well learn the answer since I might find that none of the candidate messages include that request. A 1k message encrypted with OTP, however, tells me nothing whatsoever. -- __ \/ o\ [EMAIL PROTECTED] /\__/ http://www.cluefactory.org.uk/paul/
Re: Cryptographic Algorithm Metrics
On Wed, 3 Jan 2001, Peter Fairbrother wrote: >on 3/1/01 9:25 pm, Greg Rose at [EMAIL PROTECTED] wrote: >> Goldreich... forgive me if I'm wrong. The important result, though, was >> that you need truly random input to the algorithm in an amount equal to the >> stuff being protected, or you cannot have unconditional security. > >Not so. Perfect compression with encryption works too. Sure it does. Let us know when you figure out how to do Perfect Compression. Bear
Re: Cryptographic Algorithm Metrics
Peter Fairbrother wrote: > > At Crypto a > > couple of years ago the invited lecture gave some very general results > > about unconditionally secure ciphers... unfortunately I can't remember > > exactly who gave the lecture, but I think it might have been Oded > > Goldreich... forgive me if I'm wrong. The important result, though, was > > that you need truly random input to the algorithm in an amount equal to the > > stuff being protected, or you cannot have unconditional security. > > Not so. Perfect compression with encryption works too. You can argue (reasonably, IMO) that the stuff being protected is the entropy in the stuff you first thought of, which can be no bigger than the compressed data. Cheers, Ben. -- http://www.apache-ssl.org/ben.html "There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit." - Robert Woodruff
Re: Cryptographic Algorithm Metrics
Greg Rose wrote: > > At 03:06 PM 1/3/2001 -0500, John Young wrote: > >Yes, the one-time pad. However, I wondered if Smith > >was hinting at another cipher(s) not yet publicized, > >perhaps computational -- or more exotic technology > >such as quantum, DNA, ultra-spectral and beyond. > > It always amazes me that people single out the OTP here. There are any > number of other algorithms that are unconditionally secure. The simplest is > Shamir's secret sharing, when you don't have enough shares. At Crypto a > couple of years ago the invited lecture gave some very general results > about unconditionally secure ciphers... unfortunately I can't remember > exactly who gave the lecture, but I think it might have been Oded > Goldreich... forgive me if I'm wrong. The important result, though, was > that you need truly random input to the algorithm in an amount equal to the > stuff being protected, or you cannot have unconditional security. The OTP > is just the simplest realisation of this. Don't you think that's a pretty good reason for singling it out? Is there any additional merit in the more complex realisations? Cheers, Ben. -- http://www.apache-ssl.org/ben.html "There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit." - Robert Woodruff
Re: Cryptographic Algorithm Metrics
on 3/1/01 9:25 pm, Greg Rose at [EMAIL PROTECTED] wrote: > At 03:06 PM 1/3/2001 -0500, John Young wrote: >> Yes, the one-time pad. However, I wondered if Smith >> was hinting at another cipher(s) not yet publicized, >> perhaps computational -- or more exotic technology >> such as quantum, DNA, ultra-spectral and beyond. > > It always amazes me that people single out the OTP here. There are any > number of other algorithms that are unconditionally secure. The simplest is > Shamir's secret sharing, when you don't have enough shares. I don't think secret sharing qualifies as a cipher. > At Crypto a > couple of years ago the invited lecture gave some very general results > about unconditionally secure ciphers... unfortunately I can't remember > exactly who gave the lecture, but I think it might have been Oded > Goldreich... forgive me if I'm wrong. The important result, though, was > that you need truly random input to the algorithm in an amount equal to the > stuff being protected, or you cannot have unconditional security. Not so. Perfect compression with encryption works too. >The OTP > is just the simplest realisation of this. > > Greg. Peter -- Peter Fairbrother [EMAIL PROTECTED]
Re: Cryptographic Algorithm Metrics
At 03:06 PM 1/3/2001 -0500, John Young wrote: >Yes, the one-time pad. However, I wondered if Smith >was hinting at another cipher(s) not yet publicized, >perhaps computational -- or more exotic technology >such as quantum, DNA, ultra-spectral and beyond. It always amazes me that people single out the OTP here. There are any number of other algorithms that are unconditionally secure. The simplest is Shamir's secret sharing, when you don't have enough shares. At Crypto a couple of years ago the invited lecture gave some very general results about unconditionally secure ciphers... unfortunately I can't remember exactly who gave the lecture, but I think it might have been Oded Goldreich... forgive me if I'm wrong. The important result, though, was that you need truly random input to the algorithm in an amount equal to the stuff being protected, or you cannot have unconditional security. The OTP is just the simplest realisation of this. Greg. NOTE NEW ADDRESS AND PHONE NUMBERS BELOW! Greg Rose INTERNET: [EMAIL PROTECTED] Qualcomm Australia VOICE: +61-2-9817 4188 FAX: +61-2-9817 5199 Level 3, 230 Victoria Road,http://people.qualcomm.com/ggr/ Gladesville NSW 2111232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C
Re: Fwd: from Edupage, December 22, 2000
On 3 Jan 2001, Jaap-Henk Hoepman wrote: > Except that eavesdropping on the quantum key distribution channel is _always_ > detected (by `laws of nature'), which is not true for these pressure-monitored > cables. It's not true here anymore either. Last year there was at least one group that demonstrated a mechanism for taking a doublet and making it a quartet without effecting the entanglement. Check the cypherpunks archive for the particular post, early this year. I was the one who posted it to the list. Before a larger group can see the virtue of an idea, a smaller group must first understand it. "Stranger Suns" George Zebrowski The Armadillo Group ,::;::-. James Choate Austin, Tx /:'/ ``::>/|/ [EMAIL PROTECTED] www.ssz.com.', `/( e\ 512-451-7087 -~~mm-'`-```-mm --'-
Re: Cryptographic Algorithm Metrics
dmolnar <[EMAIL PROTECTED]> writes: > On Wed, 3 Jan 2001, Ben Laurie wrote: > > > > A cipher is Conditionally Computationally Secure > > > (CCS) if the cipher could be implemented with keys > > > that are not quite "long enough" or with not quite > > > "enough" rounds to warrant a CS rating. Examples: > > > SKIPJACK and RSA. > > This seems a bit strange to me. I would have expected "conditionally" > computationally secure to mean "secure if some condition holds." > For instance, Rabin is secure if factoring is hard. Yes, I don't think these ratings are terribly coherent. By the definition you give, of course, we wouldn't be able to name any unconditionally computationally secure algorithms since we don't even know wheter P equals NP, but that's as it should be. We need different metrics for the strength of known attacks (upper bound on security) and basis in problems believed to be hard (lower bound on security). Mixing the two seems unhelpful. -- __ \/ o\ [EMAIL PROTECTED] /\__/ http://www.cluefactory.org.uk/paul/
Re: Cryptographic Algorithm Metrics
Yes, the one-time pad. However, I wondered if Smith was hinting at another cipher(s) not yet publicized, perhaps computational -- or more exotic technology such as quantum, DNA, ultra-spectral and beyond. The workshop's purpose was to discuss what security standards might be established to assure industry of adequate protection. The unspoken question was what the USG could do to help industry without making its own intelligence-gathering and law enforcement more difficult and its information security means and methods more vulnerable. That Smith downplayed the weakness of DES is odd. Surely he knows of the DES cracks and Cracker. Still, crackable systems help governments covert. Are there clues of covert cryptanalysis in Smith's table of the strength of selected algorithms: http://csrc.nist.gov/csspab/june13-15/Smith.pdf - MetricDES 3 DESSKIPJACK Key 56 112 80 Attack1.37x10^11 1.25x10^28 2.56x10^18 Time A Steps 2^56 2^1122^80 Rounds16 48 32 Strength CS CS CS - - MetricRC5 RSA Key 64 1024 Attack3.61x10^13 2.40x10^17 Time A Steps 2^56 Factoring Rounds16 N/A Strength CCS CCS - Note correction of previously cited examples: SKIPJACK is in the CS category, and RC5 should have been in CCS.
Re: Cryptographic Algorithm Metrics
On Wed, 3 Jan 2001, Ben Laurie wrote: > > A cipher is Conditionally Computationally Secure > > (CCS) if the cipher could be implemented with keys > > that are not quite "long enough" or with not quite > > "enough" rounds to warrant a CS rating. Examples: > > SKIPJACK and RSA. This seems a bit strange to me. I would have expected "conditionally" computationally secure to mean "secure if some condition holds." For instance, Rabin is secure if factoring is hard. > An example of this would be the cipher used on DVDs, or the mobile phone > one, both of whose names I've forgotten. The mobile phone one would be A5, with two variants A5/1 and A5/2. A5/1 likely qualifies as Weak, while A5/2 would now be Very Weak. -David
Re: Cryptographic Algorithm Metrics
John Young wrote: > > Last summer, at a workshop on "Security Metrics," conducted > by NIST's Computer System Security and Privacy Advisory > Board, Landgrave Smith, Institute of Defense Analysis, reported > on a pilot study of "the metrics used for determining the > strength of cryptography." > >http://csrc.nist.gov/csspab/june13-15/sec-metrics.html (the workshop) > >http://csrc.nist.gov/csspab/june13-15/Smith.pdf (Smith's presentation) > > Five catergories of algorithm strength were established for > the pilot: > > Unconditionally Secure (US) > Computationally Secure (CS) > Conditionally Computationally Secure (CCS) > Weak (W) > Very Weak (VW) > > Smith stated: "A cipher is Unconditionally Secure (US) > if no matter how much ciphertext is intercepted, there > is not enough information in the ciphertext to > determine the plaintext uniquely." > > No examples for this strength were given, and it was > not clear from Smith's presentation whether there is > such a cipher or the category was only provided > as a theoretical premise. > > Question: is there a cipher that is Unconditionally > Secure? One-time pads. > A cipher is Computationally Secure (CS) if it cannot > be broken by systematic analysis with available > resources in a short enough time to permit > exploitation. Examples: DES and 3 DES. Wrong, DES is Weak. > A cipher is Conditionally Computationally Secure > (CCS) if the cipher could be implemented with keys > that are not quite "long enough" or with not quite > "enough" rounds to warrant a CS rating. Examples: > SKIPJACK and RSA. > > A Weak (W) cipher can be broken by a brute force > attack in an acceptable length of time with an > "affordable" investment in cryptanalytic resources > (24 hours and $200K). No examples. > > A Very Weak (VW) cipher is one that can be broken > by determining the key systematically in a short > period of time with a small investment (8 hours > and $20K). No examples. An example of this would be the cipher used on DVDs, or the mobile phone one, both of whose names I've forgotten. Cheers, Ben. -- http://www.apache-ssl.org/ben.html "There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit." - Robert Woodruff
Re: Cryptographic Algorithm Metrics
As I suppose others on the list have pointed out by now, he is just plain wrong about DES. DES is not computationally secure in this terminology. It is either Conditionally Computationally Secure or Weak. Bear On Wed, 3 Jan 2001, John Young wrote: >Last summer, at a workshop on "Security Metrics," conducted >by NIST's Computer System Security and Privacy Advisory >Board, Landgrave Smith, Institute of Defense Analysis, reported >on a pilot study of "the metrics used for determining the >strength of cryptography." > > http://csrc.nist.gov/csspab/june13-15/sec-metrics.html (the workshop) > > http://csrc.nist.gov/csspab/june13-15/Smith.pdf (Smith's presentation) > >Five catergories of algorithm strength were established for >the pilot: > >Unconditionally Secure (US) >Computationally Secure (CS) >Conditionally Computationally Secure (CCS) >Weak (W) >Very Weak (VW) > >Smith stated: "A cipher is Unconditionally Secure (US) >if no matter how much ciphertext is intercepted, there >is not enough information in the ciphertext to >determine the plaintext uniquely." > >No examples for this strength were given, and it was >not clear from Smith's presentation whether there is >such a cipher or the category was only provided >as a theoretical premise. > >Question: is there a cipher that is Unconditionally >Secure? > >Mr. Smith defined the other categories: > >[Quote] > >A cipher is Computationally Secure (CS) if it cannot >be broken by systematic analysis with available >resources in a short enough time to permit >exploitation. Examples: DES and 3 DES. > >A cipher is Conditionally Computationally Secure >(CCS) if the cipher could be implemented with keys >that are not quite "long enough" or with not quite >"enough" rounds to warrant a CS rating. Examples: >SKIPJACK and RSA. > >A Weak (W) cipher can be broken by a brute force >attack in an acceptable length of time with an >"affordable" investment in cryptanalytic resources >(24 hours and $200K). No examples. > >A Very Weak (VW) cipher is one that can be broken >by determining the key systematically in a short >period of time with a small investment (8 hours >and $20K). No examples. > >[End quote] > > > > >DES - CS >3 DES - CS >SKIPJACK - CCS >RSA - CCS > > > > >
Unconditional security
John Young asks: Smith stated: "A cipher is Unconditionally Secure (US) if no matter how much ciphertext is intercepted, there is not enough information in the ciphertext to determine the plaintext uniquely." No examples for this strength were given, and it was not clear from Smith's presentation whether there is such a cipher or the category was only provided as a theoretical premise. Question: is there a cipher that is Unconditionally Secure? Yes. A one-time pad based cipher has precisely this property. They are also, however, unpleasant to use. Keep in mind that as soon as you use anything but a perfectly random keystream that is only employed once, it is no longer a one-time pad. "Pseudo" one time pads are not even remotely unconditionally secure. At best they are simply stream ciphers of ordinary security. Frequently, "pseudo" one time pad schemes are totally worthless. -- Perry E. Metzger[EMAIL PROTECTED] -- Quality NetBSD CDs, Support & Service. http://www.wasabisystems.com/
Cryptographic Algorithm Metrics
Last summer, at a workshop on "Security Metrics," conducted by NIST's Computer System Security and Privacy Advisory Board, Landgrave Smith, Institute of Defense Analysis, reported on a pilot study of "the metrics used for determining the strength of cryptography." http://csrc.nist.gov/csspab/june13-15/sec-metrics.html (the workshop) http://csrc.nist.gov/csspab/june13-15/Smith.pdf (Smith's presentation) Five catergories of algorithm strength were established for the pilot: Unconditionally Secure (US) Computationally Secure (CS) Conditionally Computationally Secure (CCS) Weak (W) Very Weak (VW) Smith stated: "A cipher is Unconditionally Secure (US) if no matter how much ciphertext is intercepted, there is not enough information in the ciphertext to determine the plaintext uniquely." No examples for this strength were given, and it was not clear from Smith's presentation whether there is such a cipher or the category was only provided as a theoretical premise. Question: is there a cipher that is Unconditionally Secure? Mr. Smith defined the other categories: [Quote] A cipher is Computationally Secure (CS) if it cannot be broken by systematic analysis with available resources in a short enough time to permit exploitation. Examples: DES and 3 DES. A cipher is Conditionally Computationally Secure (CCS) if the cipher could be implemented with keys that are not quite "long enough" or with not quite "enough" rounds to warrant a CS rating. Examples: SKIPJACK and RSA. A Weak (W) cipher can be broken by a brute force attack in an acceptable length of time with an "affordable" investment in cryptanalytic resources (24 hours and $200K). No examples. A Very Weak (VW) cipher is one that can be broken by determining the key systematically in a short period of time with a small investment (8 hours and $20K). No examples. [End quote] DES - CS 3 DES - CS SKIPJACK - CCS RSA - CCS
Re: Fwd: from Edupage, December 22, 2000
Jaap-Henk Hoepman wrote: > > On Tue, 02 Jan 2001 12:03:40 -0800 David Honig <[EMAIL PROTECTED]> writes: > > At 10:27 PM 1/1/01 +0530, Udhay Shankar N wrote: > > >Did this slip between the cracks in holiday season or has it already been > > >discussed here ? > > > > > >Udhay > > > > Its just yet another 'secure' scheme that uses quantum theory > > (here, discrete photons; elsewhere, entangled photons) > > to detect or prevent leaking bits. > > > > More elegant than gas-pressurized, pressure-monitored 'secure' cables, but > > the same idea. > > Except that eavesdropping on the quantum key distribution channel is _always_ > detected (by `laws of nature'), which is not true for these pressure-monitored > cables. I thought that detection in quantum systems was probabilistic? Cheers, Ben. -- http://www.apache-ssl.org/ben.html "There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit." - Robert Woodruff
Re: Fwd: from Edupage, December 22, 2000
On Tue, 02 Jan 2001 12:03:40 -0800 David Honig <[EMAIL PROTECTED]> writes: > At 10:27 PM 1/1/01 +0530, Udhay Shankar N wrote: > >Did this slip between the cracks in holiday season or has it already been > >discussed here ? > > > >Udhay > > Its just yet another 'secure' scheme that uses quantum theory > (here, discrete photons; elsewhere, entangled photons) > to detect or prevent leaking bits. > > More elegant than gas-pressurized, pressure-monitored 'secure' cables, but > the same idea. Except that eavesdropping on the quantum key distribution channel is _always_ detected (by `laws of nature'), which is not true for these pressure-monitored cables. Jaap-Henk -- Jaap-Henk Hoepman | Come sail your ships around me Dept. of Computer Science | And burn your bridges down University of Twente | Nick Cave - "Ship Song" Email: [EMAIL PROTECTED] === WWW: www.cs.utwente.nl/~hoepman Phone: +31 53 4893795 === Secr: +31 53 4893770 === Fax: +31 53 4894590 PGP ID: 0xF52E26DD Fingerprint: 1AED DDEB C7F1 DBB3 0556 4732 4217 ABEF
