Re: Brumley & Boneh timing attack on OpenSSL
Regarding using blinding to defend against timing attacks, and supposing that a crypto library is going to have support for blinding: - Should it do blinding for RSA signatures as well as RSA decryption? - How about for ElGamal decryption? - Non-ephemeral (static) DH key exchange? - Ephemeral DH key exchange? - How about for DSS signatures? In other words, what do we need as far as blinding support either in developing a crypto library or in evaluating a crypto library for use? Suppose we are running a non-SSL protocol but it is across a real-time Internet or LAN connection where timing attacks are possible. And suppose our goal is not to see a paper and exploit published within the next three years telling how to break the protocol's security with a few hours of connect time. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Proven Primes
Tom St Denis writes: > What is the benefit of having leading/trailing bits fixed? As far as I > know it doesn't make any form of index calculus attack any harder to > apply. The Handbook of Applied Cryptography, http://www.cacr.math.uwaterloo.ca/hac/, has a chapter on efficient implementations which might provide some insight. You can take advantage of the left FFF's by using the modular reduction algorithm described in section 14.3.4 of the HAC. This is good for the case where the modulus is slightly less than a power of 2. Or you can take advantage of the right FFF's by using Montgomery exponentiation, described in section 14.3.2 of the HAC and also in algorithm 14.94. Montgomery multiplication uses a value m' = - m^(-1) mod b, where m is the modulus and b is the bignum base, typically 2^32 or 2^64. With these moduli m' becomes 1, simplifying the calculations. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
RIAA turns against Hollings bill
The New York Times is reporting at http://www.nytimes.com/2003/01/14/technology/14CND-PIRACY.html that the Recording Industry Association of America, along with two computer and technology industry trade groups, has agreed not to seek new government regulations to mandate technological controls for copyright protection. This appears to refer primarily to the Hollings bill, the CBDTPA, which had already been struck a blow when Hollings lost his committee chairmanship due to the Democrats losing Senate leadership. Most observers see this latest step as being the last nail in the coffin for the CBDTPA. Some months ago there were those who were predicting that Trusted Computing technology, as embodied in the TCPA and Palladium proposals, would be mandated by the Hollings bill. They said that all this talk of "voluntary" implementations was just a smoke screen while the players worked behind the scenes to pass laws that would mandate TCPA and Palladium in their most restrictive forms. It was said that Linux would be banned, that computers would no longer be able to run software that we can use today. We would cease to be the real owners of our computers, others would be "root" on them. A whole host of calamaties were forecast. How does this latest development change the picture? If there is no Hollings bill, does this mean that Trusted Computing will be voluntary, as its proponents have always claimed? And if we no longer have such a threat of a mandated Trusted Computing technology, how bad is it for the system to be offered in a free market? Let technology companies decide whether to offer Palladium technology on their computers or not. Let content producers decide whether to use Palladium to protect their content or not. Let consumers decide whether to purchase and enable Palladium on their systems or not. Why is it so bad for people to freely make their own decisions about how best to live their lives? Cypherpunks of all people should be the last to advocate limiting the choices of others. Thankfully, it looks like freedom may win this round, despite the efforts of cypherpunks and "online freedom" advocates to eliminate this new technology option. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: DeCSS, crypto, law, and economics
John S. Denker writes: > The main thing the industry really had at stake in > this case is the "zone locking" aka "region code" > system. I don't see much evidence for this. As you go on to admit, multi-region players are easily available overseas. You seem to be claiming that the industry's main goal was to protect zone locking when that is already being widely defeated. Isn't it about a million times more probable that the industry's main concern was PEOPLE RIPPING DVDS AND TRADING THE FILES? Movies are freely available on the net, just like MP3s, and the DeCSS software was the initial technology that made ripping DVD's possible. Many people would rather get something for free than to pay for it, and DVD ripping allows that for movies. The MPAA obviously is afraid of following the RIAA into oblivion. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Hooray for TIA
[I'm not happy with the tone of this, but I'm forwarding it as privacy politics is pretty clearly on topic... --Perry] For years we cypherpunks have been telling you people that you are responsible for protecting your own privacy. Use cash for purchases, look into offshore accounts, protect your online privacy with cryptography and anonymizing proxies. But did you listen? No. You thought to trust the government. You believed in transparency. You passed laws, for Freedom of Information, and Protection of Privacy, and Insurance Accountability, and Fair Lending Practices. And now the government has turned against you. It's Total Information Awareness program is being set up to collect data from every database possible. Medical records, financial data, favorite web sites and email addresses, all will be brought together into a centralized office where every detail can be studied in order to build a profile about you. All those laws you passed, those government regulations, are being bypassed, ignored, flushed away, all in the name of National Security. Well, we fucking told you so. And don't try blaming the people in charge. You liberals are cursing Bush, and Ashcroft, and Poindexter. These laws were passed by the entire U.S. Congress, Republicans and Democrats alike. Representatives have the full support of the American people; most were re-elected with large margins. It's not Bush and company who are at fault, it's the whole idea that you can trust government to protect your privacy. All that data out there has been begging to be used. It was only a matter of time. And you know what? It's good that this has happened. Not only has it shown the intellectual bankruptcy of trust-the-government privacy advocates, it proves what cypherpunks have been saying all along, that people must protect their own privacy. The only way to keep your privacy safe is to keep the data from getting out there in the first place. Cypherpunks have consistently promoted two seemingly contradictory ideas. The first is that people should protect data about themselves. The second is that they should have full access and usability for data they acquire about others. Cypherpunks have supported ideas like Blacknet, and offshore data havens, places where data could be collected, consolidated and sold irrespective of government regulations. The same encryption technologies which help people protect their privacy can be used to bypass attempts by government to control the flow of data. This two-pronged approach to the problem produces a sort of Darwinian competition between privacy protectors and data collectors. It's not unlike the competition between code makers and code breakers, which has led to amazing enhancements in cryptography technology over the past few decades. There is every reason to expect that a similar level of improvement and innovation can and will eventually develop in privacy protection and data management as these technologies continue to be deployed. But in the mean time, three cheers for TIA. It's too bad that it's the government doing it rather than a shadowy offshore agency with virtual tentacles into the net, but the point is being made all the same. Now more than ever, people need privacy technology. Government is not the answer. It's time to start protecting ourselves, because nobody else is going to do it for us. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: patent free(?) anonymous credential system pre-print
Stefan Brands writes regarding http://eprint.iacr.org/2002/151/: > The paper shows some promise but, apart from being insecure, has other > drawbacks that should be addressed: > > ... My work... introduced by myself... my MIT press book... > > In addition to various other drawbacks pointed out by of Dr. Adam Back > (see [EMAIL PROTECTED]/msg02752.html), > the proposal does not offer a wallet-with-observer mode, discarding > protection, anonymous recertification / updating, multi-application > certificates, etcetera. And balanced against all these numerous shortcomings, there is one inescapable, overwhelming fact: THE AUTHORS ARE MAKING THE FRUITS OF THEIR LABOR AVAILABLE FREELY FOR THE WORLD TO USE. With all of your patents, and your writings, and your self-promotion, how many people are using your certificates in the real world? Think how much you could have accomplished, how much of a difference you could have made, if you had been willing to sacrifice the hope of great riches. Instead you have followed in the footsteps of your mentor Chaum, and both of you have withheld your talent from the world. What is it about cash and credential systems that everyone who works in the area thinks they should patent their results? All you have accomplished is to make sure that no implementations exist! What good are your great ideas if no one can use them? Look at Chaum! Is that where you want to be in 20 years? Bitter and barren? Cut off from the cryptographic community? Reduced to publishing via the government patent office? That's no life for a great mind. Creativity demands interaction with an active and vital intellectual community. You have to give in order to take. Building walls around your intellectual property shuts others out even as you shut yourself in. If you really want to accomplish something meaningful, rather than continuing to hype and shill for a system which no one can use without entering into delicate financial negotiations, why not make it available on some basis for people to experiment with? Maybe a non-commercial, open-source GPL implementation could be a starting point. There is considerable interest in reputation systems among the P2P community and credentials could be a part of that. You can still protect your commercial interests while letting people get familiar with the technology by making a non-commercial library available. That's just one possibility. The point is, your ideas are going nowhere using your present strategy. Either this technology won't be used at all, or inferior but unrestricted implementations will be explored, as in the recent work. If you want things to happen differently, you must change your strategy. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Cryptogram: Palladium Only for DRM
Peter Biddle writes:
> Pd is designed to fail well - failures in SW design shouldn't result in
> compromised secrets, and compromised secrets shouldn't result in a BORE
> attack.
Could you say something about the sense in which Palladium achieves
BORE ("break once run everywhere") resistance? It seems that although
Palladium is supposed to be able to provide content security (among
other things), a broken Palladium implementation would allow extracting
the content from the "virtual vault" where it is kept sealed. In that
case the now-decrypted content can indeed run everywhere.
This seems to present an inconsistency between the claimed strength of the
system and the description of its security behavior. This discrepancy
may be why Palladium critics like Ross Anderson charge that Microsoft
intends to implement "document revocation lists" which would let Palladium
systems seek out and destroy illicitly shared documents and even programs.
Some have claimed that Microsoft is talking out of both sides of its
mouth, promising the content industry that it will be protected against
BORE attacks, while assuring the security/privacy community that the
system is limited in its capabilities. If you could clear up this
discrepancy that would be helpful. Thanks...
-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Cryptographic privacy protection in TCPA
It looks like Camenisch & Lysyanskaya are patenting their credential system. This is from the online patent applications database: http://appft1.uspto.gov/netacgi/nph-Parser?Sect1=PTO2&Sect2=HITOFF&p=1&u=/netahtml/PTO/search-bool.html&r=1&f=G&l=50&co1=AND&d=PG01&s1=camenisch&OS=camenisch&RS=camenisch > Non-transferable anonymous credential system with optional anonymity > revocation > > Abstract > > The present invention relates to a method and system for securely > proving ownership of pseudonymous or anonymous electronic credentials. A > credential system is described consisting of users and organizations. An > organization knows a user only by a pseudonym. The pseudonyms of the > same user, established for use with different organizations, cannot be > linked. An organization can issue a credential to a pseudonym, and the > corresponding user can prove possession of this credential to another > organization that knows him under another pseudonym. During the prove of > possession of the credential nothing besides the fact that he owns such > a credential is revealed. A refinement of the credential system provides > credentials for unlimited use, so called multiple-show credentials, > and credentials for one-time use, so called one-show credentials. Some of the claims seem a little broad, like this first one: > 1. A method for establishing a pseudonym system by having a certificate > authority accepting a user as a new participant in said pseudonym system, > the method comprising the steps of: receiving a first public key provided > by said user; verifying that said user is allowed to join the system; > computing a credential by signing the first public key using a secret > key owned by said certificate authority; publishing said first public > key and said credential. Wouldn't this general description cover most proposed credential systems in the past, such as those by Chaum or Brands? Does anyone know how to contact the PTO regarding proposed patents, perhaps to point out prior art? - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Palladium and malware
Bill Frantz writes, regarding the possibility that the Palladium architecture could be designed to resist the use of encrypted code: > All general purpose computers require a way to move data space to code > space to support compilation. Well, this is usually done by storing the data to the disk, and then later loading it as a program file. It does not prevent data and code memory from being distinct, which was the proposal for how Palladium could reduce the risk of being used to run encrypted code. If a Palladium program was forced to go through the disk, that is, to load data, decrypt it, store it to the disk, and then load it as code, then that would provide a means to get access to the unencrypted code, defeating the goal of keeping the code within the "vault". > Even if you don't allow compilation, most > modern systems have enough different powerful scripting languages that > interpretation is sufficient to support viruses. It's not clear why these languages would use the Palladium features and run their scripts in the shielded mode. But you're right that if they did, this could provide a mechanism for disassembly-resistant code. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Palladium and malware
Paul Crowley asks: > I'm informed that malware authors often go to some lengths to prevent > their software from being disassembled. Could they use Palladium for > this end? Are there any ways in which the facilities that Palladium > and TCPA provide could be useful to a malware author who wants to > frustrate legitimate attempts to understand and defeat their software? Palladium provides a "curtained" memory area where software is supposed to be relatively free from being accessed or modified. (Apparently it can be configured to be debugged when in this area by the use of "test keys".) If disassembling a program requires access to it in memory, then this curtained memory region could present an obstacle to disassembling. However in most cases the memory would be loaded from the disk so having access to the program on disk would allow you to disassemble it just as well as if it were in memory. From what has been said about Palladium, it will not support encrypted programs. However that might not stop a determined malware author from having the program encrypt itself when it first runs (using the "virtual vault" concept) and store the encrypted version on the disk, deleting the original plaintext version. The Palladium vault technology would then make it impossible for any other software to decrypt that data. The malware might not be able to use the regular Palladium program loader to run its encrypted portion, but conceivably it could "manually" load that encrypted data into the curtained area, decrypt it using a key accessible only to itself, and then run. This would still leave the program vulnerable until the first time it runs, but afterwards it would be impossible to get at the program text in the clear. A program could reduce its window of vulnerability if it were distributed in encrypted form, using a key that would be provided by a remote server - which could even be any other infected computer! The program stub would start up, use Palladium attestation to connect reliably to another virus-corrupted instance of itself on the net, and receive a global, system-wide key. This key would be kept locked in the "virtual vault" and would decrypt the remainder of the program, which could then run in the curtained area. Even if all instances of the virus shared the same key or set of keys, it would be impossible for non-virus programs or programmers to get access to the key except by hacking their hardware, scraping out a key, and creating a virtual Palladium system. So the main question at this point is how program code and/or data gets loaded into the curtained area, and whether it would be possible to load encrypted data into that area, decrypt it and then run it as code. There is a computer design called the Harvard architecture which has a strict separation between code and data space, and conceivably Palladium could use a similar approach to make it impossible to run decrypted code. Adopting this approach would add credibility to Microsoft's promises not to use Palladium for software copy protection. But if they don't go to such an extreme, it is likely that Palladium would allow the use of various techniques to help malware hide from its opponents. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Cryptographic privacy protection in TCPA
Carl Ellison suggested an alternate way that TCPA could work to allow for revoking virtualized TPMs without the privacy problems associated with the present systems, and the technical problems of the elaborate cryptographic methods. Consider first the simplest possible method, which is just to put a single signature key in each TPM and allow the TPM to use that to sign its messages on the net. This is reliable and allows TPM keys to be revoked, but it obviously offers no privacy. Every usage of a TPM key can be correlated as coming from a single system. TCPA fixed this by adding a trusted third party, the "Identity CA" who would be the only one to see the TPM key. But Carl offers a different solution. Instead of burning only one key into the TPM, burn several. Maybe even a hundred. And let these keys be shared with other TPMs. Each TPM has many keys, and each key has copies in many TPMs. Now let the TPMs use their various keys to identify themselves in transactions on the net. Because each key belongs to many different TPMs, and the set of TPMs varies for each key, this protects privacy. Any given usage of a key can be narrowed down only to a large set of TPMs that possess that key. If a key is misused, i.e. "scraped" out of the TPM and used to create a virtualized, rule-breaking software TPM, it can be revoked. This means that all the TPMs that share that one key lose the use of that key. But it doesn't matter much, because they each have many more they can use. Since it is expected that only a small percentage of TPMs will ever need their keys revoked, most TPMs should always have plenty of keys to use. One problem is that a virtualized TPM which loses one of its keys will still have others that it can use. Eventually those keys will also be recognized as being mis-used and be revoked as well. But it may take quite a while before all the keys on its list are exhausted. To fix this, Carl suggests that the TPM manufacturer keep a list of all the public keys that are in each TPM. Then when a particular TPM has some substantial fraction of its keys revoked, that would be a sign that the TPM itself had been virtualized and all the rest of the keys could be immediately revoked. The precise threshold for this would depend on the details of the system, the number of keys per TPM, the number of TPMs that share a key, the percentage of revoked keys, etc. But it should not be necessary to allow each TPM to go through its entire repertoire of keys, one at a time, before a virtualized TPM can be removed from the system. Carl indicated that he suggested this alternative early in the TCPA planning process, but it was not accepted. It does seem that while the system has advantages, in some ways it shares the problems of the alternatives. It provides privacy, but not complete privacy, not as much as the cryptographic schemes. And it provides security to the TPM issuers, but not complete security, not as much as the Privacy CA method. In this way it can be seen as a compromise. Often, compromise solutions are perceived more in terms of their disadvantages than their benefits. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Chaum's unpatented ecash scheme
Ben Laurie writes: > Note that the scheme as described (and corrected) is vulnerable to > marking by the bank, and so is not anonymous. This is discussed and > fixed in my paper on Lucre > (http://anoncvs.aldigital.co.uk/lucre/theory2.pdf). Actually the scheme described based on Chaum's talk (corrected for probable typos) is essentially what you describe in your paper as the Type II Defence, in section 5. Your analysis shows that it is not vulnerable to marking and is anonymous. Speaking of anonymous, you should give credit in your paper to Anonymous for discovering the possibility of marking Lucre coins, in a coderpunks posting at http://www.mail-archive.com/coderpunks@toad.com/msg02186.html, and for inventing the Type II Defence, both in the posting above and amplifed at http://www.mail-archive.com/coderpunks@toad.com/msg02323.html. It may seem pointless to credit anonymous postings, but it makes the historical record more clear. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Chaum's unpatented ecash scheme
David Chaum gave a talk at the Crypto 2002 conference recently in which he briefly presented a number of interesting ideas, including an approach to digital cash which he himself said would "avoid the ecash patents". The diagram he showed was as follows: Optimistic Authenticator z = x^s Payer f(m)^a z^b Bank -> [f(m)^a z^b]^s <- m, f(m)^s -> It's hard to figure out what this means, but it bears resemblance to a scheme discussed on the Coderpunks list in 1999, a variant on a blinding method developed by David Wagner. See http://www.mail-archive.com/coderpunks@toad.com/msg02323.html for a description, with a sketch of a proof of blindness at http://www.mail-archive.com/coderpunks@toad.com/msg02387.html and http://www.mail-archive.com/coderpunks@toad.com/msg02388.html. In Chaum's diagram it is not clear which parts of the key are private and which public, although z is presumably public. Since the bank's action is apparently to raise to the s power, s must be secret. That suggests that x is public. However Chaum's system seems to require dividing by (z^b)^s in order to unblind the value, and if s is secret, that doesn't seem possible. In Wagner's scheme everything was like this except that the bank's key would be expressed as x = z^s, again with x and z public and s secret. f(m) would be a one-way function, which gets doubly-blinded by being raised to the a power and multiplied by z^b, where a and b are randomly chosen blinding factors. The bank raises this to its secret power s, and the user unblinds to form f(m)^s. To later deposit the coin he does as in the third step, sending m and f(m)^s to the bank. For the unblinding, the user can divide by (z^b)^s, which equals z^(b*s), which equals (z^s)^b, which equals x^b. Since x is public and the user chose b, he can unblind the value. Maybe the transcription above of the Chaum scheme had a typo and it was actually similar to the Wagner method. Chaum commented that the payer does not receive a signature in this system, and that he doesn't need one because he is protected against misbehavior by the bank. This is apparently where the scheme gets its name. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: adding noise blob to data before signing
Eugen Leitl asked: > 1) What's the name of the technique of salting/padding an small integer >I'm signing with random data? You shouldn't need to salt/pad with random data, fixed data should be OK. > 2) If I'm signing above short (~1 kBit) sequences, can I sign them >directly, or am I supposed to hash them first? (i.e. does a presence >of an essentially fixed field weaken the signature) Derek Atkins replied: > It depends on the signature algorithm. With RSA you can sign any > message "directly" if said message is smaller than the public key size > (N). DSA, however, requires the use of a hash. Actually, depending on the data being signed, it can be important to hash for RSA. After all, RSA is existentially forgeable: anyone can forge a signature on a *random* value (if C=M^e mod n, then M is a signature on C). They might be able to try some large number of sigs until they got a random value which looked enough like legitimate data to be accepted - especially possible if the 1kbit value being signed holds dense, random-ish binary data. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Montgomery Multiplication
On Tue, 2 Jul 2002, Damien O'Rourke wrote: > I was just wondering if anyone knew where to get a good explanation of > Montgomery multiplication for the non-mathematician? I have a fair bit > of maths but not what is needed to understand his paper. Bear replied: > Montgomery Multiplication is explained for the computer scientist > in Knuth, _Seminumerical Methods_. > > Briefly: The chinese remainder theorem proves that for any set > A1...AN of integers with no common divisors, any integer X which is > less than their product can be represented as a series of remainders > X1...XN, where Xn is equal to X modulo An. > > if you're using the same set of integers with no common divisors > A1...AN to represent two integers X and Y, you have a pair of series > of remainders X1...XN and Y1...YN. > > Montgomery proved that Z, the product of X and Y, if it's in the > representable range, is Z1...ZN where Zn equals (Xn * Yn) mod An. That's not Montgomery multiplication; that's what Knuth called modular arithmetic, described in section 4.3.2 of Seminumerical Methods. Montgomery multiplication is well described at http://www.ciphergoth.org/writing/postings/news-992.txt, as Paul Crowley posted. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Ross's TCPA paper
Ross Anderson writes: > During my investigations into TCPA, I learned that HP has started a > development program to produce a TCPA-compliant version of GNU/linux. > I couldn't figure out how they planned to make money out of this. On > Thursday, at the Open Source Software Economics conference, I figured > out how they might. > ... > The business model, I believe, is this. HP will not dispute that the > resulting `pruned code' is covered by the GPL. You will be able to > download it, compile it, check it against the binary, and do what you > like with it. However, to make it into TCPA-linux, to run it on a > TCPA-enabled machine in privileged mode, you need more than the code. > You need a valid signature on the binary, plus a cert to use the TCPA > PKI. That will cost you money (if not at first, then eventually). H Not clear that this really works to make money. The GPL allows everyone to redistribute HP's software verbatim, right? So a cert on one copy of the software will work on everyone's. How can HP make money on a product that everyone can copy freely, when they can all share the same cert? It's true that modified versions of the software would not be able to use that cert, and it would no doubt be expensive to get a new cert for the modified software. But that still gives HP no monopoly on selling or supporting its own version. Anyone can step in and do that. Is the cert itself supposed to be somehow copyrighted? Kept secret? Will it be illegal to publish the cert, to share it with someone else? This seems pretty questionable both in terms of copyright law (since a cert is a functional component) and in terms of the GPL (which would arguably cover the cert and forbid restrictively licensing it). It seems more likely that the real purpose is to bring the benefits of TCPA to the Linux world. As an innovator in this technology HP will gain in reputation and be the source that people turn to for development and support in this growing area. The key to making money from open source is reputation. Being first makes good economic sense. You don't need conspiracy theories. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Ross's TCPA paper
Lucky Green writes regarding Ross Anderson's paper at: http://www.ftp.cl.cam.ac.uk/ftp/users/rja14/toulouse.pdf > I must confess that after reading the paper I am quite relieved to > finally have solid confirmation that at least one other person has > realized (outside the authors and proponents of the bill) that the > Hollings bill, while failing to mention TCPA anywhere in the text of the > bill, was written with the specific technology provided by the TCPA in > mind for the purpose of mandating the inclusion of this technology in > all future general-purpose computing platforms, now that the technology > has been tested, is ready to ship, and the BIOS vendors are on side. It's an interesting claim, but there is only one small problem. Neither Ross Anderson nor Lucky Green offers any evidence that the TCPA (http://www.trustedcomputing.org) is being designed for the support of digital rights management (DRM) applications. In fact if you look at the documents on the TCPA web site you see much discussion of applications such as platform-based ecommerce (so that even if a user's keys get stolen they can't be used on another PC), securing corporate networks (assuring that each workstation is running an IT-approved configuration), detecting viruses, and enhancing the security of VPNs. DRM is not mentioned. Is the claim by Ross and Lucky that the TCPA is a fraud, secretly designed for the purpose of supporting DRM while using the applications above merely as a cover to hide their true purposes? If so, shouldn't we expect to see the media content companies as supporters of this effort? But the membership list at http://www.trustedcomputing.org/tcpaasp4/members.asp shows none of the usual suspects. Disney's not there. Sony's not there. No Viacom, no AOL/Time/Warner, no News Corp. The members are all technology companies, including crypto companies like RSA, Verisign and nCipher. Contrast this for example with the Brodcast Protection Discussion Group whose ongoing efforts are being monitored by the EFF at http://www.eff.org/IP/Video/HDTV/. There you do find the big media companies. That effort is plainly aimed at protecting information and supporting DRM, so it makes sense that the companies most interested in those goals are involved. But with the TCPA, the players are completely different. And unlike with the BPDG, the rationale being offered is not based on DRM but on improving the trustworthiness of software for many applications. Ross and Lucky should justify their claims to the community in general and to the members of the TCPA in particular. If you're going to make accusations, you are obliged to offer evidence. Is the TCPA really, as they claim, a secretive effort to get DRM hardware into consumer PCs? Or is it, as the documents on the web site claim, a general effort to improve the security in systems and to provide new capabilities for improving the trustworthiness of computing platforms? - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Shortcut digital signature verification failure
David Wagner describes a trick from Dan Bernstein to speed up RSA signature verification with e = 3: > One of the nicest ideas from his work is easy to describe. In plain > RSA, s is a valid signature on m if H(m) = s^3 (mod n). Now suppose we > ask the signer to also supply an integer k such that 0 <= s^3 - kn < n; > clearly this can't hurt security, as k can be publicly computed from s. > Then the recipient can efficiently verify the validity of the claimed > signature (t,k) on m as follows: verify that 0 <= s^3 - kn < n; then So the signer supplies s and k. And our first step is to verify that 0 <= s^3 - kn < n. But given that we've computed S = s^3 - kn and it is in this range, isn't it the case that S = s^3 mod n? And so we can test test that H(m) = S = s^3 mod n and that verifies the signature directly. > secretly pick a random 31-bit prime p, compute t' = s^3 mod p, n' = > n mod p, k' = k mod p, h' = H(m) mod p, and verify that t' - k'n' = h' > (mod p). - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Lucky's 1024-bit post [was: RE: objectivity and factoring analysis
Wei Dai writes: > Using a factor base size of 10^9, in the relationship finding phase you > would have to check the smoothness of 2^89 numbers, each around 46 bits > long. (See Frog3's analysis posted at > http://www.mail-archive.com/cryptography%40wasabisystems.com/msg01833.html. > Those numbers look correct to me.) If you assume a chip that can check > one number per microsecond, you would need 10^13 chips to be able to > complete the relationship finding phase in 4 months. Even at one dollar > per chip this would cost ten trillion dollars (approximately the U.S. > GDP). This is probably not the right way to approach the problem. Bernstein's relation-finding proposal to directly use ECM on each value, while asymptotically superior to conventional sieving, is unlikely to be cost-effective for 1024 bit keys. Better to extrapolate from the recent sieving results. http://citeseer.nj.nec.com/cavallar00factorization.html is the paper from Eurocrypt 2000 describing the first 512 bit RSA factorization. The relation-finding phase took about 8000 MIPS years. Based on the conventional asymptotic formula, doing the work for a 1024 bit key should take about 10^7 times as long or 80 billion MIPS years. For about $200 you can buy a 1000 MIPS CPU, and the memory needed for sieving is probably another couple of hundred dollars. So call it $500 to get a computer that can sieve 1000 MIPS years in a year. If we are willing to take one year to generate the relations then ($500 / 1000) x 8 x 10^10 is $40 billion dollars, used to buy approximately 80 million cpu+memory combinations. This will generate the relations to break a 1024 bit key in a year. If you need it in less time you can spend proportionately more. A $400 billion dollare machine could generate the relations in about a month. This would be about 20% of the current annual U.S. federal government budget. However if you were limited to a $1 billion budget as the matrix solver estimate assumed, the machine would take 40 years to generate the relations. > BTW, if we assume one watt per chip, the machine would consume 87 trillion > kWh of eletricity per year. The U.S. electricity production was only 3.678 > trillion kWh in 1999. The $40 billion, 1-year sieving machine draws on the order of 10 watts per CPU so would draw about 800 megawatts in total, adequately supplied by a dedicated nuclear reactor. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
ecash news: Brands & credentica.com
For cpunxnews/cryptography: Seems people missed this anonymous note about Dr Stefan Brands new company http://www.credentica.com on cypherpunks -- interesting news -- will Credentica persue ecash, private credentials, more liberal licensing terms than digicash and ecash-technologies/infospace. (Brands ecash and credential patent suite is the only major contender to Chaum's patent suite. Chaum's patent suite was recently acquired by Infospace for an undisclosed amount from ecash-technologies which earlier bought the patents when digicash filed for chapter 11 bankruptcy.) > To: [EMAIL PROTECTED] Cc: [EMAIL PROTECTED] Cc: [EMAIL PROTECTED] Subject: Brands credentica (Re: [Tsg] Micropayments & VISA?) Your information is out of date: Brands is no longer at ZKS, last month a new company was launched in which Brands is involved, see www.credentica.com, the rights are not tangled up in any way (legal separation, all rights cleared). Paul Holman wrote: > [...] There are possible alternatives; Brands' patents, now tied up > at ZKS, and other schemes which try to body swerve Chaum, but > nothing comforting. < - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Bernstein's NFS machine
James Donald writes: > On Tue, Feb 26, 2002 at 02:04:16AM -, Frog3 wrote: > > The cost [To factor RSA 1024] is the need to build a > > machine that can do 53 billion simultaneous, independent > > ECM factorizations for smoothness testing. It's not clear > > how amenable this would be to hardware implementation. > > > > A time of 2^71 is considerably less threatening than 2^53. > > If I understand frog3's numbers correctly: > > If one builds extraordinarily massive hardware capable of > dowing 53 billion simultaneous independent ECM > factorizations, Bernstein's method wil take 2^71 steps. > > Assuming that the massively parallel hardware does fifty > billion factorizations each microsecond, then it will take > Bernstein's super duper hardware about one hundred million > years to factor an RSA 1024 modulus. No, this is not quite right. The 2^71 is the cost in terms of elementary operations (add, xor, etc.). This is based on 2^53 ECM factorizations per machine times 2^18 operations per factorization. James' quoted time would be correct if the machine could do 50 billion *operations* per microsecond (a clock rate of 50,000,000 gigahertz (50 petahertz), compared to 1-2 gigahertz available today). This fast machine would then take 100 million years to break a 1024 bit key. Even though these are "back of the envelope" calculations which ignore o(1) terms that could theoretically be negative, the basic principles seem sound. The need to do 2^89 tests to get enough relations for a factor base of 2^36 is based on the known fraction of multi-hundred bit numbers that are going to be smooth. This value doesn't have much "wiggle room". You could try to use a smaller factor base, but the size of the values to be tested for smoothness is going to be in the hundreds of bits, and reducing the factor base will make it even harder to find smooth values. The 2^18 estimate for the cost of the ECM smoothness test will likewise be hard to improve on significantly. In addition, with a factor base of size 2^36 and testing numbers up to ten times longer, each ECM factorizer will have to do approximately 10 factorizations before it can determine smoothness. Even with the uncertainties, this calculation seems to be strong enough to say that this machine cannot pose a threat to 1024 bit keys using near-term technology. You can assume impossibly large numbers of an impossibly fast machine, and it still takes an impossibly large time. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Bernstein's NFS machine
David Wagner writes: > Bernstein's analysis is based on space*time as your cost metric. > What happens if we assume that space comes for free, and we use simply > time as our cost metric? Do his techniques lead to an improvement in > this case? Bernstein basically treats memory and processing elements as interchangeable to a first approximation. After all, it's just different ways of laying out silicon. So assuming that space comes for free is equivalent to assuming that you have an infinite number of processors to bring to bear on the problem. > It looks to me like there is no improvement in the first phase, but > there is some improvement in the second phase (reduction in time from > B^2 to B^1.5). If you had an unlimited number of processors for the first phase, and you have X number of values to check for smoothness, then you can use X processors and run one test on each value, completing the whole thing in time L^o(1). This does not reduce Bernstein's cost metric but it would reduce the time considerably. I don't think such a speedup is possible with the sieving approach. However this is not physically reasonable, as the number of values to be tested for smoothness is approximately L^2, which would be on the order of 2^90 for a 1024 bit key. If each cell were .01 microns on a side you would still need 100,000 square kilometers of chip area. So this extrapolation is not very meaningful. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Bernstein's NFS machine
More analysis of Dan Bernstein's factoring machine from http://cr.yp.to/papers.html#nfscircuit.; The NFS algorithm has two phases. The first searches for coefficients (a,b) from some interval which are relatively prime and which satisfy two smoothness bounds. The smoothness is with respect to a factor base consisting of all primes less than some bound. (Actually there may be two or more bounds used for different tests, but that complication will be ignored here.) Each success produces one relation and will be one row of a matrix whose columns correspond to the primes in the factor base. Once enough relations are collected (more rows than columns) the second phase begins. This involves looking for linear dependencies among the rows of the matrix, where the math is in GF(2). Once a dependency is found, the corresponding rows can be combined to produce a value with two different square roots, which with good probability will lead to a factorization of n. Dan Bernstein proposes methods to significantly reduce the cost (defined as space times time) of both phases. L is defined as exp(log(n)^(1/3) * log(log(n))^(2/3)), where n is the number to be factored. It is a key parameter for the work cost of the NFS class of algorithms. n L - 2^512 2^33 2^1024 2^45 2^1536 2^54 2^2048 2^61 Let E represent the bound on the (a,b) coefficient values which are searched. Then E^2 values will be checked for relative primality and smoothness. Let B represent the bounds on the factor base. A smooth value is one for which all of its factors are less than B. In previous work, sieving is used to test for smoothness, which is in part where the Number Field Sieve algorithm gets its name. Sieving E^2 values over a factor base of size B takes roughly E^2 log log B time and B space. We will ignore the log log B factor and just say E^2 and B space, for a total work factor of B*E^2. With a factor base of size B, roughly B relations have to be found. Then a sparse B by B matrix must be solved in the second phase. Using conventional algorithms this solution takes roughly B^2 work on a machine that has B space. The total work factor is B^3. For optimum balance, the work factor of these two phases is set equal, giving B^3 = B*E^2, or B=E. It is also necessary that E be large enough to produce at least B relations. This leads to the solution E = B = L^0.961. The corresponding work factor is this value cubed, or L^2.883. (Dan Bernstein gives a slightly lower figure due to an improvement by Don Coppersmith.) Bernstein improves on both of these phases. He points out that for sufficiently large n, it will be less work to determine smoothness by simply trying to factor each value using the Elliptic Curve factoring method (ECM). This is the best factoring method known for finding relatively small factors, as is required here. Attempting to factor E^2 values over a factor base of size B takes time proportional to E^2 times a function of B which is larger than that in the sieve case, but still asymptotically small compared to E^2. So the time is basically proportional to E^2 as with the sieve. The savings comes in the space. The sieve requires an array to hold the primes in the factor base, and an array to represent the values being sieved. The most efficient approach is to set these two arrays to roughly the same size, breaking the input into pieces of size B. This does not slow the algorithm but allows it to run in space B as assumed above. In contrast, the ECM algorithm requires no large storage spaces. It does not have to store the factor base or any representation of a large block of numbers to be checked. It simply runs the ECM factoring algorithm on each value to be checked until it either finds a factor or times out. If it finds one, it divides it out and repeats the process with the residue. Eventually the residue is small enough that we know the number is smooth, or the algorithm fails indicating that the value is not smooth. Storage requirements are minimal. Based on this, the ECM approach takes time proportional to E^2 and space essentially a constant, for a total work of E^2. This is compared with B*E^2 for the sieve. Bernstein also improves on the second phase, finding a dependency among the rows of the matrix. It still requires space of size B to hold the sparse matrix of size B by B. But by making the matrix elements be active instead of dumb memory cells, he can accelerate the matrix operations that are necessary. The result is that finding the dependencies is reduced to taking time B^1.5 rather than B^2. The total work is then B^2.5. For optimality these two phases are balanced with E^2 = B^2.5 or E=B^1.25. Incorporating the requirement that E be big enough to generate the necessary B relations, the solution is E=L^0.988 and B=L^0.790. The total work is E^2 or L^1.976. This is compared to the L^2.883 value above, a significant savings. It is interesting t
Re: CFP: PKI research workshop
PHB: > PKI is in widespread use, it is just not that noticeable when you use it. > This is how it should be. SSL is widely used to secure internet payment > transactions. PM: > HTTPS SSL does not use PKI. Could someone define PKI (beyond just what it stands for, Public Key Infrastructure)? It looks like you are all talking past each other by using the term to mean different things. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: "Pirate Utopia," FEED, February 20, 2001
Adam Back wrote: > To elaborate on this slightly. There are inherent reasons why > steganography is harder than encryption: the arms race of hiding data > in noise is based on which side (the hider vs the detecter) has the > best understanding of the characteristics of the host signal. The > problem is the host signal is not something with clear definition, > what is known is primarily empirical statistical analysis. > Manipulating signals with noise in them to replace noise with the > stego text is not so hard, but knowing and modeling the signal and the > source noise is not a solvable problem. If you read the report at http://www.citi.umich.edu/techreports/reports/citi-tr-01-11.ps.gz you will find that the authors, Niels Provos and Peter Honeyman, you find that they actually found a great many images with statistical indication of steganographic content: "After processing the two million images with Stegdetect, we find that over 1% of all images seem to contain hidden content." That is, these images seemed to depart from normal statistics to a significant degree. The question is whether these are random variations from the norm or are they actual embedded content? This is the factor which the analysis above seems to neglect. Any statistical test is going to have a certain number of false positives. This provides a background of "noise" (that is, false positives) in which a true signal (a true positive, an image with actual steganographic content) can hide. The Stegdetect paper proceeded to further analyze the 2+ images by looking for passwords that would produce meaningful messages from the hypothesized hidden content, via dictionary attack. No valid passwords were found, and the authors concluded therefore that these were all false positives. This does not seem to be a fully supported conclusion. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: "Pirate Utopia," FEED, February 20, 2001
Adam Back writes: > Also it's interesting to note that it appears from Niels Provos and > Peter Honeymans paper that none of the currently available stego > encoding programs are secure. They have broken them all (at least I > recognise the main stego programs available in their list of systems > their tools can attack), and it appears that all of the stego encoders > are naive attempts. No, Provos' own system, Outguess, www.outguess.org, is secure in the latest version. At least, he can't break it. It remains to be seen whether anyone else can. See the papers on that site. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: chip-level randomness?
Ted Tso writes: > It turns out that with the Intel 810 RNG, it's even worse because > there's no way to bypass the hardware "whitening" which the 810 chip > uses. Hence, if the 810 random number generator fails, and starts > sending something that's close to a pure 60 HZ sine wave to the > whitening circuitry, it may be very difficult to detect that this has > happened. The "whitener" is just a slightly improved von Neumann bias remover. The tradition vN state machine looks at pairs of bits and does something like this: 0 0 -> discard 0 1 -> output 1 1 0 -> output 0 1 1 -> discard This removes a static bias. I.e. if you are producing say 55% 0's and 45% 1's, after this whitener you will output 50% 0's and 1's. However it is at the cost of discarding a considerable fraction of the bits. The improved version in the Intel RNG has a 3 bit window and this lets it remove the bias just as well while discarding somewhat fewer bits. If the internal circuitry did output a 60Hz sine wave then regularities would still be visible after this kind of whitener. It is a rather mild cleanup of the signal. It doesn't seem right to object to them including a bias remover. They have done other things to reduce bias. For example they use a pair of thermal resistors located next to each other on the chip and use the difference of the values from each of them, to reduce sensitivity to environmental influences. This reduces bias, but should they have left the differencing out so that you could more easily measure a possible influence? Suppose the voltage were to drop to this part of the chip; the differencing will hide this fact and prevent you from detecting that maybe some other parts aren't working well. Here is an example of a possible partial-failure mode which the chip internal design will tend to hide. It should not be considered a design flaw for the chip to do this. It improves the random numbers which the chip produces. And similarly, the digital bias remover does the same thing. The bottom line is the quality of the random numbers produced by the device. It is designed internally to withstand various kinds of noise and bias, so as to produce the best random numbers possible. See http://www.cryptography.com/intelRNG.pdf for information on the design of the RNG. See if you can identify a plausible failure mode which could be detected if the whitener was not present, but which will be undetectable with the vN whitener in place. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
