Re: quantum chip built
On Sat, 14 Jan 2006, Michael Cordover wrote: > In order to factor a 1024 > bit modulus you'd need a 1024 bit QC. Perhaps if there were some sudden > breakthrough it'd be a danger in a decade - but this is the same as the > risk of a sudden classical breakthrough: low. This is not necessarily so. In order to factor a 1024-bit modulus using Shor's algorithm, you would indeed need a 1024- qbit machine. But we haven't seen what fruit may be borne by algorithm research and hybrid machinery; it seems plausible that a hybrid machine may be able to use, say, 16 qbits to divide the work factor of factoring large numbers in general by approx. 65536. In general, I think that until QC is a mature field, cryptographers and cryptologists ought to assume that some QC or hybrid algorithm or machinery that may be discovered "any minute now" can simultaneously exploit the strengths of both QC and classical computation. And that means, in general, that I'd want to *add* the number of bits factorable by Shor's algorithm in the foreseeable future to the number of bits factorable by classical brute-force algorithms. In fact, maybe we ought to be worried about synergistic effects and multiplying the figures together, although I can't imagine where such effects would come from. Let us say simply that Quantum Computing is far from mature, and at this moment we are only beginning to understand it. I remember all the mechanical engineers who proved that no heavier-than-air flying machine could exist back in the 19th century, back when knowledge of mechanics and materials was less precise than now... And these guys knew what there was to know about it. I'm chary of people "proving" that no n-bit factoring machine can be built just because the way they already know to build one (Shor's algorithm, which requires n qbits) won't work. Given that our knowledge of QC is nascent, our ignorance of QC's practical limits is likely staggering, and caution is to be advised. Bear - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
standards being adopted for encrypting stored data
http://www.networkworld.com/news/2005/121505-tape-encryption.html "Proposed standards for protecting data on disk or tape are gathering steam within the IEEE and could be supported in products as soon as next year, according to proponents." --Steven M. Bellovin, http://www.cs.columbia.edu/~smb - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
NY Times reports that spy program is not narrowly targeted
According to President Bush, the illegal NSA domestic espionage program he ordered was narrowly targeted against people known to have Al Qaeda links. However, it appears that, as with his previous false claims that espionage only happened with a warrant, that this claim was on its face untrue: Spy Agency Data After Sept. 11 Led F.B.I. to Dead Ends By LOWELL BERGMAN, ERIC LICHTBLAU, SCOTT SHANE and DON VAN NATTA Jr. Published: January 17, 2006 WASHINGTON, Jan. 16 - In the anxious months after the Sept. 11 attacks, the National Security Agency began sending a steady stream of telephone numbers, e-mail addresses and names to the F.B.I. in search of terrorists. The stream soon became a flood, requiring hundreds of agents to check out thousands of tips a month. But virtually all of them, current and former officials say, led to dead ends or innocent Americans. F.B.I. officials repeatedly complained to the spy agency that the unfiltered information was swamping investigators. The spy agency was collecting much of the data by eavesdropping on some Americans' international communications and conducting computer searches of phone and Internet traffic. Some F.B.I. officials and prosecutors also thought the checks, which sometimes involved interviews by agents, were pointless intrusions on Americans' privacy. [...] President Bush has characterized the eavesdropping program as a "vital tool" against terrorism; Vice President Dick Cheney has said it has saved "thousands of lives." But the results of the program look very different to some officials charged with tracking terrorism in the United States. [...] "We'd chase a number, find it's a schoolteacher with no indication they've ever been involved in international terrorism - case closed," said one former F.B.I. official, who was aware of the program and the data it generated for the bureau. "After you get a thousand numbers and not one is turning up anything, you get some frustration." [...] Rest of article at: http://www.nytimes.com/2006/01/17/politics/17spy.html I again plead with all of you who care about the future your children live in to call your congressional representatives and demand that action be taken. Congress has already largely forgotten about this -- a few weeks is a long time in the memories of politicians. It is up to you remind them. If you do not, you will have no one to blame but yourself. "All that is necessary for evil to succeed is that good men do nothing." -- Edmund Burke Perry - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
RE: quantum chip built
> >From what I understand simple quantum computers can easily > brute-force attack RSA keys or other types of PK keys. Is > ECC at risk too? And are we at risk in 10, 20 or 30 years from now? Quantum computers break RSA, cryptosystems based on discrete log over finite fields, and cryptosystems based on discrete log over elliptic curves, where "break" means "reduce to polynomial time". The best description of the ECC variant of Shor's quantum algorithm is in Proos and Zalka's "Shor's discrete logarithm quantum algorithm for elliptic curves", http://arxiv.org/abs/quant-ph/0301141. They estimate that ~1000 qubits are needed to break a 160-bit ECC key (as opposed to ~2000 qubits for a 1024-bit RSA key). NTRU and HFE-based schemes (such as QUARTZ and SFLASH) aren't currently known to be broken by quantum algorithms -- there are proposed quantum algorithms that may square-root the time to break NTRU, but this isn't a reduction to polynomial time. I don't know if anyone's looked at quantum computers as applied to HFE. Cheers, William - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: long-term GPG signing key
Travis H. wrote: Why the heck am I expiring encryption keys each year? Anyone who records the email can crack it even if the key is invalid by then. All it really does is crudely limit the quantity of data sent under that key, which is little to none anyway. If your threat model includes attacks on the system(s) you use to decrypt messages, or rubber hose/subpoena key-cracking, expiring *and wiping* confidentiality keys limits the time during which the keys can be compromised using those methods. -- Blogzilla:>http://dooom.blogspot.com/ Say no to ID cards! http://www.pledgebank.com/refuse2 - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Echelon papers leaked
In 1996, New Zealander Nicky Hager wrote a book "Secret Power" containing a great deal of information on Echelon, with a particular NZ perspective. A few days ago, papers held by the Prime Minister of the time were accidentally released and appeared in the Sunday Star Times. Some quotes from the story at http://www.stuff.co.nz/stuff/sundaystartimes/0,2106,3540743a6005,00.html: The top-secret intelligence report found among David Lange's papers shows New Zealand had been spying on friendly countries throughout the region. Targets included Japanese and Philippines diplomatic cables and the government communications of Fiji, the Solomons, Tonga and "international organisations operating in the Pacific". The Government Communications Security Bureau's 1985/86 annual report also reveals that one of New Zealand's main targets was "UN diplomatic" cables, but which agencies of the United Nations were targeted is not stated. [...] "A total of 171 reports were published, covering the Solomons, Fiji, Tonga and international organisations operating in the Pacific. The raw traffic for this reporting provided by NSA the US National Security Agency)." The GCSB also produced 238 intelligence reports on Japanese diplomatic cables, using "raw traffic from GCHQ/NSA sources". This was down from the previous year: "The Japanese government implementation of a new high grade cypher system seriously reduced the bureau's output." For French government communications, the GCSB "relied heavily on (British) GCHQ acquisition and forwarding of French Pacific satellite intercept". [...] Each page of the 31-page report that mentioned eavesdropping operations was headed "TOP SECRET UMBRA HANDLE VIA COMINT CHANNELS ONLY". COMINT stands for "communications intelligence". There's also a second story at http://www.stuff.co.nz/stuff/sundaystartimes/0,2106,3540733a6005,00.html covering US pressure on NZ over its anti-nuclear policy. Peter. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: long-term GPG signing key
Guus Sliepen wrote: > It depends on how it is used. For example, when I sent this email, I > typed in the passphrase of my PGP key, authorising GnuPG to create a > signature for this email. This comes very close to "human signing". I > read, understood, approve etc. with the contents of this email. > > If assymetric cryptography is used to automatically sign a credit card > transaction without the user having to do more than click a button, then > I agree that in that situation, the digital signature is not the same as > a human signature. but as in some of the PKI forays into non-repudiation and human signatures ... there was no way for a relying party to determine the difference ... and in the previous thread of digital signature dual-use vulnerability, this can open up fraud. at one point, some were assuming if there was a digital certificate with the non-repudiation flag set, then the digital signature indicated human signature (read, understood, agrees, approves, and/or authorizes). however, nothing in various PKI protocols providing for proving which digital certificate was actually appended to a particular digital signature (appending a non-repudiation digital certificate might imply the creation of some obligation associated with a digital signature used as a human signature; however there was no protocol provisions for establishing which form of digital signature was actually intended and/or which digital certificate was actually appended to any particular operaion). the dual-use vulnerability has an environment where servers nominally transmit random data for signing (one of the possible countermeasures for replay attack) and the person generates a digital signature on the random data w/o having looked at the data (assuming purely authentication operation). the other party has actually substituted some sort of valid text in place of the valid data and then asserts that the person has performed the digital signature implying a human signature (read, understood, agrees, approves, and/or authorizes) as opposed to implying pure authentication operation. the crook may attempt to further substantiate the fraudulent claim by producing a digital certificate (for the corresponding public key) with the non-repudiation bit set (and PKI protocols lack provisions for differentiating which, of possible several, digital certificates might actually have been attached). the possible dual-use for digital signatures then may lead to enormous ambiguity since the basic technology only provides for authentication ... and that w/o significant additional business processes it is difficult to differentiate digital signatures used for purely authentication purposes and the grossly embellished purposes associated with human signatures. any embellishing of digital signatures for human signature purposes, in turn creates significant additional risk than straight-forward authentication. a basic issue isn't what you intended when you caused a digital signature to be created ... but what can any relying-party reasonably expect that you intended ... and what can the relying-party reasonably rely on. then if there is any possible ambiguity as to what you may have intended when a digital signature was created, can an attacker use the existence of such ambiguity to perpetrate fraud (aka dual-use vulnerability). - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: long-term GPG signing key
On Sat, Jan 14, 2006 at 12:30:25PM -0700, Anne & Lynn Wheeler wrote: > Guus Sliepen wrote: > > By default, GPG creates a signing key and an encryption key. The signing > > key is used both for signing other keys (including self-signing your own > > keys), and for signing documents (like emails). However, it is possible > > to "split" the signing key into a master key that you only use to sign > > other keys, and a key dedicated to signing documents. You can revoke the > > latter key and create a new one whenever you want, the master key is > > still valid. Also, when people sign your key, they sign your master key, > > not the subkeys. The signatures you accumulated will also still be > > valid. You can also keep the master key safely tucked away on an old > > laptop that you keep in a safe, and only export the subkeys to your > > workstation. That way the master key is very safe. > as in previous post ... i assert that fundamental digital signature > verification is an authentication operation > http://www.garlic.com/~lynn/aadsm22.htm#5 long-term GPG signing keys > > and doesn't (by itself) carry with it characteristics of human > signature, read, understood, approves, agrees, and/or authorizes. It depends on how it is used. For example, when I sent this email, I typed in the passphrase of my PGP key, authorising GnuPG to create a signature for this email. This comes very close to "human signing". I read, understood, approve etc. with the contents of this email. If assymetric cryptography is used to automatically sign a credit card transaction without the user having to do more than click a button, then I agree that in that situation, the digital signature is not the same as a human signature. [...] > it is when you start equating private keys with certification and truth > characteristics that you move into a completely different risk and > threat domain. I don't equate private keys with that. I do equate signatures made with those keys with that. > the other foray into embellishing private keys and digital signatures > with human signature type characteristics was the non-repudiation > activity. however, it is now commoningly accepted that to embellish > digital signatures with non-repudiation attributes requires a whole lot > of additional business processes ... not the simple operation of > generating an authentication digital signature. [...] > the corollary is that digitally signed certificates and > private keys embellished with certification and truth characteristics > become less and less meaningful. That is probably true, but in the mean time Travis still wants to know how to create a PGP key with the properties he wishes for. -- Met vriendelijke groet / with kind regards, Guus Sliepen <[EMAIL PROTECTED]> signature.asc Description: Digital signature
Re: long-term GPG signing key
Guus Sliepen wrote: > By default, GPG creates a signing key and an encryption key. The signing > key is used both for signing other keys (including self-signing your own > keys), and for signing documents (like emails). However, it is possible > to "split" the signing key into a master key that you only use to sign > other keys, and a key dedicated to signing documents. You can revoke the > latter key and create a new one whenever you want, the master key is > still valid. Also, when people sign your key, they sign your master key, > not the subkeys. The signatures you accumulated will also still be > valid. You can also keep the master key safely tucked away on an old > laptop that you keep in a safe, and only export the subkeys to your > workstation. That way the master key is very safe. as in previous post ... i assert that fundamental digital signature verification is an authentication operation http://www.garlic.com/~lynn/aadsm22.htm#5 long-term GPG signing keys and doesn't (by itself) carry with it characteristics of human signature, read, understood, approves, agrees, and/or authorizes. the PKI & CA hiearchical infrastructures does tend to add those attributes to digital signature operations ... creating an equiivalence between certification digital signatures (and the private keys that produce such digital signatures) and the validity of the information being certified. if you are starting to create a class of private keys that start to carry the attribute of whether something is true or not (i.e. the information being certified) ... then there can start to become some confusion between the difference between the private key as an authentication mechanism and the use of the private key as whether something is true or not. I would assert that authentication private keys can be treated like a much better password technology ... not having various of the shared-secret vulnerabilities and other shortcomings. it is when you start equating private keys with certification and truth characteristics that you move into a completely different risk and threat domain. the other foray into embellishing private keys and digital signatures with human signature type characteristics was the non-repudiation activity. however, it is now commoningly accepted that to embellish digital signatures with non-repudiation attributes requires a whole lot of additional business processes ... not the simple operation of generating an authentication digital signature. the whole scenario of digital signing of public keys ... is a matter of the entity performing the digital signing doing an authentication operation ... but that the entity is certifying the truth of some value ... typically related to the public key. that is a whole business process infrastructure that has to be layered on top of digital signatures (in much the same way to actually achieve non-repudiation a whole business process infrastructure has to be created that is built above any authentication digital signature). the other characteristics is that stale, static certification ... paper or digitally signed electronic bits ... are characteristic of the offline age ... where an entity could present the certificate representing the truth of some information; as opposed to the relying party having their own access to the truth of the same information. in the transition to an online world, it is becoming less & less coming that relying parties won't have access to the truth of some piece of information (making certificates and credentials less and less meaningful). the corollary is that digitally signed certificates and private keys embellished with certification and truth characteristics become less and less meaningful. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: quantum chip built
At 03:04 AM 1/14/2006 +1100, Michael Cordover wrote: John Denker wrote: [EMAIL PROTECTED] wrote: From what I understand simple quantum computers can easily brute-force attack RSA keys or other types of PK keys. My understanding is that quantum computers cannot "easily" do anything. Au contraire, quantum computers can easily perform prime factoring or perform discrete logarithms - this is Shor's algorithm and has been known for more than a decade. The difficulty is in making a QC. Is ECC at risk too? And are we at risk in 10, 20 or 30 years from now? ECC is also at risk because it relies on the difficulty of discrete logarithms which are victim to a quantum attack. Are we at risk in 10, 20 or 30 years? Well, as John said, it's hard to say. The first working 2 qbit computers were demonstrated in 1998, then 3 qbits in the same year. 7 qbits were demonstrated in 2000. 8 in December 2005. As you can see, adding a qbit is pretty hard. In order to factor a 1024 bit modulus you'd need a 1024 bit QC. Perhaps if there were some sudden breakthrough it'd be a danger in a decade - but this is the same as the risk of a sudden classical breakthrough: low. My assessment: nothing to worry about for now or in the immediate future. A key valid for 20 years will face much greater dangers from expanding classical computer power, weak implementations, social engineering etc. The "quantum chip" is just a new housing, not anything that puts RSA or ECC at risk. Hmm, extrapolating forward... 1998 = 2 qubits 2005 = 8 qubits (a 4x increase in 7 years) 2013 = 32 qubits? 2020 = 128 qubits? 2027 = 512 qubits? 2034 = 2048 qubits? So, say, somewhere between 20 to 30 years from now current RSA moduli may possibly be at risk from the Shor's algorithm. Is that a reasonable assumption? If so, would ECC (moduli) also be at risk within this time frame? - Alex -- - Alex Alten - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
RE: long-term GPG signing key
Alexander Klimov wrote:
>On Wed, 11 Jan 2006, Ian G wrote:
>> Even though triple-DES is still considered to have avoided that trap,
>> its relatively small block size means you can now put the entire
>> decrypt table on a dvd (or somesuch, I forget the maths).
> This would need 8 x 2^{64} bytes of storage which is approximately
> 2,000,000,000 DVD's (~ 4 x 2^{32} bytes on each).
> Probably, you are referring to the fact that during encryption of
> a whole DVD, say, in CBC mode two blocks are likely to be the
> same since there are an order of 2^{32} x 2^{32} pairs.
I've actually seen something like this happen in real life.
As you know, RSA has been running a series of 'Secret Key
Challenges', wherein we ask people to try to brute-force
messages encrypted with RC5 at various keystrengths. There is
a cash prize for the person turning in the correct response.
The messages are encrypted in CBC mode with 32 bit blocks.
The start of the message has a known plaintext
Most of the recent challenges have been won by distributed.net.
While they were working on the 64 bit challenge, I received an
email saying that a proposed solution had been found, and was asked
to check it. (We set up the challenges in such a way that the
correct keys are unknown, even to us).
The supplied key correctly decrypted the first block, but the
rest were gibberish. After scratching our heads, we realized
that d.net had found a collision.
It was almost a year later they found the correct key, for the
$10,000 prize. They immediately started on the 72 bit challenge.
(I'm not holding my breath).
Peter Trei
-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: long-term GPG signing key
On Thu, 12 Jan 2006 00:48:05 -0600, Travis H said: > All it really does is crudely limit the quantity of data sent under > that key, which is little to none anyway. And it has the advantage that people will stop sending encrypted mail to this key after the expiration date. Comes handy if you forgot your passphrase or lost physical access to the key. Shalom-Salam, Werner - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: long-term GPG signing key
In message <[EMAIL PROTECTED]>, Ian G writes:
>Alexander Klimov wrote:
>> On Wed, 11 Jan 2006, Ian G wrote:
>>
>>
>>>Even though triple-DES is still considered to have avoided that
>>>trap, its relatively small block size means you can now put the
>>>entire decrypt table on a dvd (or somesuch, I forget the maths).
>>
>>
>> This would need 8 x 2^{64} bytes of storage which is approximately
>> 2,000,000,000 DVD's (~ 4 x 2^{32} bytes on each).
>>
>> Probably, you are referring to the fact that during encryption of a
>> whole DVD, say, in CBC mode two blocks are likely to be the same
>> since there are an order of 2^{32} x 2^{32} pairs.
>
>Thanks for the correction, yes, so obviously I
>muffed that one. I saw it mentioned on this list
>about a year ago, but didn't pay enough attention
>to recall the precise difficulty that the small
>block size of 8 bytes now has.
The difficulty with 3DES's small blocksize is the 2^32 block limit when
using CBC -- you start getting collisions, allowing the attacker to
start building up a code book. The amount of data is quite within
reach at gigabit speeds, and gigabit Ethernet is all but standard
equipment on new computers. Mandatory arithmetic: 2^32 bytes is 2^38
bits, or ~275 * 10^9. At 10^9 bits/sec, that's less than 5 minutes.
Even at 100M bps -- and that speed *is* standard today -- it's less
than an hour's worth of transmission. The conclusion is that if you're
encrypting a LAN, you need AES or you need to rekey fairly often.
--Steven M. Bellovin, http://www.cs.columbia.edu/~smb
-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: quantum chip built
Steven M. Bellovin wrote: http://www.wired.com/news/technology/0%2c70001-0.html?tw=wn_tophead_5 They seems to have built a device which can store one qubit, isolated from the rest of the world. They seem to be able to scale up their technique to store many qubits, but I strongly suspect that they cannot store those many qubits COHERENTLY. To store reliably individual qubits is not that difficult, but to prevent entangled systems from interacting with the environment is very, very difficult. Maybe someone else can give more information? -- Mads Rasmussen LEA - Laboratório de Ensaios e Auditoria (Cryptographic Certification Laboratory) Office: +55 11 4208 3873 Mobile: +55 11 9655 8885 Skype: mads_work http://www.lea.gov.br - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: quantum chip built
John Denker wrote: [EMAIL PROTECTED] wrote: From what I understand simple quantum computers can easily brute-force attack RSA keys or other types of PK keys. My understanding is that quantum computers cannot "easily" do anything. Au contraire, quantum computers can easily perform prime factoring or perform discrete logarithms - this is Shor's algorithm and has been known for more than a decade. The difficulty is in making a QC. Is ECC at risk too? And are we at risk in 10, 20 or 30 years from now? ECC is also at risk because it relies on the difficulty of discrete logarithms which are victim to a quantum attack. Are we at risk in 10, 20 or 30 years? Well, as John said, it's hard to say. The first working 2 qbit computers were demonstrated in 1998, then 3 qbits in the same year. 7 qbits were demonstrated in 2000. 8 in December 2005. As you can see, adding a qbit is pretty hard. In order to factor a 1024 bit modulus you'd need a 1024 bit QC. Perhaps if there were some sudden breakthrough it'd be a danger in a decade - but this is the same as the risk of a sudden classical breakthrough: low. My assessment: nothing to worry about for now or in the immediate future. A key valid for 20 years will face much greater dangers from expanding classical computer power, weak implementations, social engineering etc. The "quantum chip" is just a new housing, not anything that puts RSA or ECC at risk. Regards, Michael Cordover -- http://mine.mjec.net/ - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
