Re: Brumley Boneh timing attack on OpenSSL
- Original Message - From: Nomen Nescio [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Monday, March 24, 2003 1:20 PM Subject: 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? If you are a client, and you manually control the signature generation (like you use PGP to sign email messages), I wouldn't implement blinding. But if you are a server (or a client that automatically responds to requests) that signs message for some reason, and you receive many requests, I would. RSA decryption, yes for servers. - How about for ElGamal decryption? - Non-ephemeral (static) DH key exchange? Again, if you are automatically answer to requests, yes I would. In the Freedom network, servers had non-ephemeral keys and did a DH key exchange with clients (client side used ephemeral keys and was anonymous), we implemented blinding on the server side to counter timing attacks because we had a hunch that they could work over network connections. - Ephemeral DH key exchange? No, I wouldn't. I would be very surprised if you could do timing attacks on one execution of a modulo exponentiation, unless there is some way to trick a server in using the same secret on different inputs, even though it's suppose to do ephemeral DH. - How about for DSS signatures? Yes if you automatically answer to requests. Paul Kocher's initial paper on the subject explicitly mentions DH, RSA and DSS. If there is a possibility that you can be used as an oracle, and you have a static key, you should be careful. --Anton - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Diffie-Hellman 128 bit
Well, I'm attacking a protocol, I know the rules of DH parameters, and the issue here is I'm trying to solve x, brute forcing that in the 128 bit range can be difficult, and x doesn't have to be a prime. (a = g^x mod P). Their primes are 128 bit primes, as well as their pubkeys, I've done some tests on their prime, and all perform under this method of (p-1)/2 = prime. This eliminates the pohlig-hellman discrete logarithm attack, but I'm trying to learn the Gaussian integer method. No, just use the Number Field Sieve algorithm (this is mentioned in section 3.5 of the manuscript I gave you the link to). You could read section 3.6 of the Handbook of Applied Cryptography for a basic introduction to the problem of discrete logarithm. --Anton - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Diffie-Hellman 128 bit
- Original Message - From: NOP [EMAIL PROTECTED] To: Derek Atkins [EMAIL PROTECTED] Cc: [EMAIL PROTECTED] Sent: Friday, March 14, 2003 9:32 PM Subject: Re: Diffie-Hellman 128 bit Well, I'm attacking a protocol, I know the rules of DH parameters, and the issue here is I'm trying to solve x, brute forcing that in the 128 bit range can be difficult, and x doesn't have to be a prime. (a = g^x mod P). Their primes are 128 bit primes, as well as their pubkeys, I've done some tests on their prime, and all perform under this method of (p-1)/2 = prime. This eliminates the pohlig-hellman discrete logarithm attack, but I'm trying to learn the Gaussian integer method. Sorry, I mentioned using NFS in my previous reply, which is probably not the way you want to go about this (since it's not as efficient for small values and more complicated to code). Index-Calculus with Gaussian integers is indeed a good way. You can look at the paper from LaMacchia and Odlyzko http://citeseer.nj.nec.com/lamacchia91computation.html which Derek and maybe someone else pointed out.. They easily calculated discret logs modulo a 192-bit integer. --Anton - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Cryptoprocessors compliant with FIPS 140-2
The list of all FIPS 140-1 and 140-2 validated modules can be found here http://csrc.nist.gov/cryptval/140-1/1401val.htm (this includes software and hardware modules). For Mitigation of Other Attacks, the FIPS 140 evaluation doesn't look at these. Some vendors might consider these attacks and implement some kind of protection, but these will not be evaluated. Documentation for a specific module might discuss countermeasures to these attacks if they have been implemented. --Anton - Original Message - From: Damien O'Rourke [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Friday, March 21, 2003 11:14 AM Subject: Cryptoprocessors compliant with FIPS 140-2 Hi, I was wondering if anyone could list a number of cryptographic processors that are compliant with the Federal information processing standard (FIPS) 140-2 Security Requirements for cryptographic modules. I know that the IBM-4758 was compliant with FIPS 140-1 up to level 4 but I don't think it has been tested under the newer version of the standard (correct me if I'm wrong). Specifically I am wondering about section 4.11 on page 39 entitled Mitigation of Other Attacks which discusses, power analysis, timing attacks, TEMPEST and fault induction. If you could tell me what level they have been certified to and where I might find some more information on them that would be great. In fact, any relevant information would be greatly appreciated. Thanks for your time. Best Regards, Damien. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED] - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Diffie-Hellman 128 bit
- Original Message - From: NOP [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Thursday, March 13, 2003 4:48 PM Subject: Diffie-Hellman 128 bit I am looking at attacks on Diffie-Hellman. The protocol implementation I'm looking at designed their diffie-hellman using 128 bit primes (generated each time, yet P-1/2 will be a prime, so no go on pohlig-hellman attack), 128-bit prime DH would be trivially breakable, maybe you mean that it uses128-bit secret keys (and a larger prime, such as 512-bit prime at least)? In any case, you can probably get all the information you are looking for in this manuscript: http://crypto.cs.mcgill.ca/~stiglic/Papers/dhfull.pdf Cheers! --Anton - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Proven Primes
- Original Message - From: tom st denis [EMAIL PROTECTED] To: Cryptography [EMAIL PROTECTED] Sent: Tuesday, March 11, 2003 11:28 AM Subject: Re: Proven Primes --- Tero Kivinen [EMAIL PROTECTED] wrote: SOPHIE GERMAIN PRIME SEARCH FIXED 64 bits. INDEX 0: PRIME (bits 512), index = 131, 0.989151 seconds: 0xc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b 139b22514a08798e3404ddef9519b3cd3a439d 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. No, but you can speed up modulo multiplication. The OAKLEY RFC says: The high order 64 bits are forced to 1. This helps the classical remainder algorithm, because the trial quotient digit can always be taken as the high order word of the dividend, possibly +1. The low order 64 bits are forced to 1. This helps the Montgomery- style remainder algorithms, because the multiplier digit can always be taken to be the low order word of the dividend. At one point in time some of my colleagues got the optimization with the high order bits set to 1 in C code going on very well, I don`t remember if we implemented the optimization with the low order bits set to 1. --Anton - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: prime proofs
The contribution of Pratt was to be the first to publish a proof that the certificate can be verified in polynomial time (thus proving that PRIMES is in NP). --Anton - Original Message - From: Richard Schroeppel [EMAIL PROTECTED] To: [EMAIL PROTECTED] Cc: David Wagner [EMAIL PROTECTED] Sent: Friday, March 07, 2003 5:06 PM Subject: prime proofs Dave Wagner writes ... Here's a simple method, due to Pratt. ... People were doing this fourty years before Pratt's paper. See, for example, Dick Lehmer's 1933 paper Hunting Big Game in the Theory of Numbers, where he describes proving primality for a 19 digit divisor of 2^95+1. It's on my web page at http://www.cs.arizona.edu/~rcs/biggame4 Or see Math. Comp. in the early 1970s for examples with more depth in the recursions. Rich Schroeppel[EMAIL PROTECTED] - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED] - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Scientists question electronic voting
- Original Message - From: Ed Gerck [EMAIL PROTECTED] [...] For example, using the proposed system a voter can easily, by using a small concealed camera or a cell phone with a camera, obtain a copy of that receipt and use it to get money for the vote, or keep the job. And no one would know or be able to trace it. But that brings up my point once again: These problems already exist with current paper-ballot voting schemes, what exactly are you trying to achieve with an electronic voting scheme? To you simply want to make the counting of the votes more reliable, and maintain the security of all other aspects, or improve absolutely everything? --Anton - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Proven Primes
I thought that finding them was the hard part, and verifying one once found was relatively easy. I used the probable prime test in the Java BigInteger package. It sounds like, from some of the list traffic, that there are better tests. Chapter 4 of the HAC gives a good introduction to all of this. http://www.cacr.math.uwaterloo.ca/hac/about/chap4.pdf There are probabilistic primality tests (e.g. Miller-Rabin), there are primality proving algorithms (e.g. Jacoby Sum Test, ECPP), some of which give a certificate of primality that can be verified using a different algorithm. Some of the tests work on integers of special forms (e.g. Mersenne numbers), others work on all integers. There are also algorithms that generate integers that are guaranteed to be prime (e.g. Maurer's algorithm), these are not tests... --Anton - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Proven Primes
- Original Message - From: Ben Laurie [EMAIL PROTECTED] To: Cryptography [EMAIL PROTECTED] Sent: Thursday, March 06, 2003 6:47 AM Subject: Proven Primes I'm looking for a list or lists of sensibly sized proven primes - all the lists I can find are more interested in records, which are _way_ too big for cryptographic purposes. I'm not aware of such a list. If you can't find any you can generate the list yourself using ECPP (Elliptic Curve Primality Proving), an implementation of which is available here http://www.lix.polytechnique.fr/~morain/Prgms/ecpp.english.html The result of ECPP is guaranteed (no probability of error), and provides a certificate of primality for integers that are proven to be prime. A competing algorithm is the Jacobi Sums test, but it is much more complicated, so implementation errors are not to be disregarded, with ECPP the verification of a primality certificate is simple to implement, so you can make sure that there were no errors in the implementation of the proving algorithm. There is also the new algorithm by Agrawal, Kayal and Saxena, but I don't believe that it is efficient in practice for the sizes of integers you are looking at. Also note that if you assume the Extended Riemann Hypothesis (ERH) to be true, you can use the Miller-Rabin algorithm in a deterministic fashion in polynomial time with no probability error. The ECPP package is easy to use and fast. The site gives benchmarks for proving 512-bit primes: Pentium III (450MHz)4.4 sec Solaris 5.7 9.5 sec Alpha EV56 (500MHz) 4 sec I suggest you generate potential Sophie Germain primes q using your favorite library (I use OpenSSL for example) and then use the ECPP package to verify that in fact both q and 2q + 1 are really prime. --Anton - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Scientists question electronic voting
- Original Message - From: Bill Frantz [EMAIL PROTECTED] To: Ed Gerck [EMAIL PROTECTED]; [EMAIL PROTECTED] Sent: Thursday, March 06, 2003 2:14 AM Subject: Re: Scientists question electronic voting [..] The best counter to this problem is widely available systems to produce fake photos of the vote, so the vote buyer can't know whether the votes he sees in the photo are the real votes, or fake ones. The easiest way to implement is to let people photograph the paper on the sample/practice -- not for real voting -- machine that poll workers use to teach voters how to use the real machines. An extortionist could provide their own camera device to the voter, which has a built in clock that timestamps the photos and does some watermarking, or something like that, which could complicate the counter-measures. But this problem already exists with current non-electronic voting scheme. It depends on the value attributed to a vote (would an extortionist be willing to provide these custom devices?). --Anton - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Scientists question electronic voting
- Original Message - From: Ed Gerck [EMAIL PROTECTED] [...] This is not possible for current paper ballots, for several reasons. For example, if you take a picture of your punch card as a proof of how you voted, what is to prevent you -- after the picture is taken -- to punch another hole for the same race and invalidate your vote? Or, to ask the clerk for a second ballot, saying that you punched the wrong hole, and vote for another candidate? The same happens for optical scan cards. These proofs are easily deniable and, thus, have no value to prove how the voter actually voted. Likewise, electronically, there is no way that a voter could prove how he voted, even if the confirmation screen does list all the choices that the voter has chosen, if that screen has two buttons: go back, confirm, and a suitable logic. After the voter presses confirm the voter sees a thank you screen without any choices present. The logic canbe set up in such a way in terms of key presses and intermediate states that even photographing the mouse cursor on a pressed confirm button does not prove that the voter did not take the mouse out and, instead, pressed the go back button to change his choices. Well the whole process can be filmed, not necessarily photographed... It's difficult to counter the attack. In you screen example, you can photograph the vote and then immediately photograph the thank you, if the photographs include the time in milliseconds, and the interval is short, you can be confident to some degree that the vote that was photographed was really the vote that was casted. You can have tamper resistant film/photograph devices and whatever you want, have the frames digitally signed and timestamped, but this is where I point out that you need to consider the value of the vote to estimate how far an extortionist would be willing to go. --Anton - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Proven Primes
- Original Message - From: Ben Laurie [EMAIL PROTECTED] To: Anton Stiglic [EMAIL PROTECTED] [Talking about the ECPP package...] I'm not convinced any of those binaries are going to run on my system (which is FreeBSD), and anyway, if I'm going to use a binary to do ECPP I may as well shove it through Mathematica - much prettier UI :-) Is their no free implementation of ECPP? Is there at least a free verifier? It's been a while since I tried it, I don't remember which platform and OS I used (a pentium with some sort of Linux) but I know that I didn't have any problems using it. I think that ECPP comes with a Maple certificate verifier, which might be what you are looking for. I think you can also convert certificates to Mathematica format. So once you have these certificates of primality it's easy to verify them. But I haven't tried any of those features... --Anton - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: [Bodo Moeller bodo@openssl.org] OpenSSL Security Advisory: Timing-based attacks on SSL/TLS with CBC encryption
Bodo Moeller wrote: Actually there are three choices: Pad-then-encrypt-then-MAC Pad-then-MAC-then-encrypt MAC-then-pad-then-encrypt It's true that pad-then-encrypt-then-MAC appears to be the safest approach in general, but pad-then-MAC-then-encrypt would also have avoided these attacks. By Pad-t-MAC-t-encrypt, do you mean a scheme where the MAC is also encrypted, or is left aside (the encrypt and authenticate method). There are problems with the latter as well, see appendix C of the paper from Krawczyk... If it's the first, then I guess that what you mean by Pad-t-MAC-t-encrypt is that you first pad the message (and IV and whatever other context) such that when you append the MAC (e.g 160 bits with SHA1-MAC) to the ciphertext the resulting size is a multiple of the block cipher size. So when you decrypt, you don't check the padding, but then after verifying the MAC you would take out the padding (and I guess verify it...). You can't play with the padding, because the MAC will fail. But if you are using CBC-DES as a MAC, you need to make sure that the MAC is verified first, not check the padding first, if not you *might* fall in to a similar trap (I'm not certain a vulnerability would exist in that context, but it sounds plausible). [...] The attack demonstrated by Vaudenay et al. users a less subtle timing difference (the difference between a MAC on about 256 SHA-1 input blocks and no MAC at all), but switching to Pad-then-MAC-then-encrypt should be considered for TLS 1.1. Pad-t-MAC-t-encrypt sounds like an interesting avenue, but why would you propose that for TLS 1.1 instead of just proposing the safe Pad-t-Encrypt-t-MAC? If there is going to be a change, might as well go with something that is provably secure, or is there some reason (compatibility or something) to prefer Pad-t-MAC-t-Encrypt that I do not see here? --Anton - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: [Bodo Moeller bodo@openssl.org] OpenSSL Security Advisory: Timing-based attacks on SSL/TLS with CBC encryption
If I'm not mistaken, the OpenSSL spec says that you should MAC the (compressed) message, and then encrypt the message and the MAC. This composition is not generically secure, on the other hand you can prove some nice things about the composition encrypt-then- MAC assuming certain conditions, see for example David Wagner's post on sci.crypt for a discussion about that: http://groups.google.ca/groups?q=sci.crypt+encrypt+then+authenticate+Wagner; hl=enlr=ie=UTF-8oe=UTF-8selm=aj77jo%241ko%241%40agate.berkeley.edurnum= 1 (using CBC-DES with a random IV and then HMAC, with a KDF that derives independent keys for the encryption and the MACing (the KDF in SSL looks like it can do this) would satisfy these conditions.) I now always recommend encrypt-then-MAC. If SSL required encrypt-then-MAC, a programmer would more naturally start by verifying the MAC, then decrypt the message, so Vaudenay's attack would be caught first by the MAC verification and the implementation would probably return an error after the MAC verification and not leak the information needed to discover the plaintext. So even though the attack is not directly the result of the SSL protocol spec, a spec which would favor encrypt-then-MAC would be better in my point of view and the security holes relating to this SSLattack in implementations might have much less of a chance of existing. --Anton - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: password based key-wrap (Re: The Crypto Gardening Guide and Planting Tips)
- Original Message - From: Adam Back [EMAIL PROTECTED] To: Peter Gutmann [EMAIL PROTECTED] Cc: [EMAIL PROTECTED]; [EMAIL PROTECTED]; Adam Back [EMAIL PROTECTED] Sent: Thursday, February 06, 2003 8:07 PM Subject: password based key-wrap (Re: The Crypto Gardening Guide and Planting Tips) [...] Or is the problem that the above ensemble is ad-hoc (though using standardised constructs). Or just that the ensemble is ad-hoc and so everyone will be forced to re-invent minor variations of it, with varying degrees of security. One of the problems is exactly that. There is no known proof of security for PBKDF2 (it might be possible to come up with one, but to the best of my knowledge nobody did so far). Ironically, there are some proofs of security for the older version of the same standard, PBKDF1 (which was replaced by PBKDF2 only because the output of PBKDF1 was of fixed length, so you couldn't derive much key material). You can prove some things about PBKDF1 relating to the fact that an adversary cannot compute the result of PBKDF1 without having to compute a certain required amount of hashes (this is the stretching part). The details of that are in the paper Secure Applications of Low-Entropy Keys by Kelsey, Schneier, Hall and Wagner: http://www.counterpane.com/low-entropy.pdf But I do think that PBKDF2 sounds reasonable, and I wouldn't be surprised if we can prove something about it's security in some reasonable model. I would use PBKDF2 if I needed to wrap a session key with only a password. In general, the problems with existing proposed key derivation functions is that they are all based on ad-hoc constructions. There is a skunks work group trying to come up with a proposal for a key derivation function which is based on some provable secure results. --Anton - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: question about rsa encryption
RSA is subject to blinding attacks and several other failure modes if used without padding. For details on what that means, read the cyclopedia cryptologia article on RSA. http://www.disappearing-inc.com/R/rsa.html That brings on another amateur question. In that article it says, If the public exponent is less than a quarter of the modulus, RSA can be insecure. Read the section on Hastad's Broadcast Attack from Boneh's excellent survey paper Twenty years of attacks on the RSA cryptosystem The paper covers these basic facts about RSA, you can get it at http://crypto.stanford.edu/~dabo/pubs.html The section on RSA in HAC will also answer your question. --Anton - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: EU Privacy Authorities Seek Changes in Microsoft 'Passport'
- Original Message - From: bear [EMAIL PROTECTED] [Talking about Microsoft Passport...] But it's even worse than that, because people who ought to know better (and people who *DO* know better, their own ethics and customers' best interests be damned) are even *DEVELOPING* for this system. It just doesn't make any damn sense. It does make some sense. The more people who are developing the system who know better, the more they may influence higher management. I'm sure that you know that in a big company like Microsoft, it's not the developer, architect or cryptographer that decides what is shipped out, but managers who don't care about security but more about $. The more security-conscious people who start working for Microsoft, the better, they will have more power to influence the decisions of higher management. Microsoft has the most widely used software products, it's a good place for someone to try to influence good security practices. If you are a security person or cryptographer, you can either decide to work for some small company which has good security practices and your opinions be highly considered, but their products not widely spread, or for a big company with widely spread products but which has bad security practices, and try to change things (even though your opinions are less considered). In which case does the security person or cryptographer have the most impact on the world of software security? --Anton - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Shamir factoring machine uninteresting?
I worte - implemented?), and 3-4 orders is not that big of a magnitude. I take that back. When considering cost, 3-4 orders of magnitude is important. --Anton - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Key Pair Agreement?
I do not know what the proper terminology is to discuss this. Assuming there is none, I will call the solution Key Pair Agreement. Call it kosherized public key generation. Kosherization is not a term often used in theoretical cryptography, but it is often used in practice It would seem that the DSA key structure facilitates this: 1. Scott sends SEED1 to Alice. 2. Alice picks a random number SEED2. 3. Alice sets SEED=SHA1(SEED1 || SEED2). 4. Alice generates a set of DSA parameters P, Q, G using the algorithm in Appendix 2, FIP-186-2. 5. Alice generates a key pair (x,y) using the parameters from (4). 6. Alice sends SEED2, counter, P, Q, G, y to Scott. 7. Scott generates P', Q', G' based on SEED=SHA1(SEED1 || SEED2), counter, and compares them to P, Q, G. Hold on, what you have kosherized is the public parameters of DSA, but you haven't really kosherized the public key, y (IINM). Given P, Q, G (chosen by say Scott, or kosherized by Alice), Alice could come up with a cooked-up public key y. It would seem difficult to impose some structure on y, since Scott will want to choose a random x, in which case G^y % P will look random. This is different from RSA, where the public key is the pair e, N, e can be set to 3, and you can impose some structure on N (as Wagner pointed out). --Anton - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Key Pair Agreement?
I can see how Alice can easily generate two primes whose product will have that *high* order part, but it seems hard to generate an RSA modulus with a specific *low* order 64 bits. It is easy in both cases, here are examples I easily came up with: (low order DEADBEEF)) p = A093CD75C6B7A577B99897B323BE30936448D25E6F0E3ED3FC6FEA2BD8229B62994A\ 4ECB72A6C54BBC4A5A7D38192D857602A016E7821D113F47200754547826C27B6993\ D43B8977BC20199C9C0EE2DA2BA63A55A73EE108787295AAE717E30D9AE257741899\ 9D0C4B447BA62B2D95A9CC90E3939206A03FD21D5503DEADBEEF q = BDDA82F4039620F351EBAEA1EC4AC4D3595DFBE44CB9554669419182720AE6E6113F\ 4EF79CAB365072E37B06CBF33237E639B500F31BEBBF12E262D4ECA1D3F0FE823BC2\ D2C77EF793A0991290203240C8EC5DA9354726038CD2EC2F42B189E68C53E09FF24C\ 28871F753AE721FB0726A6536AC38EEB645161596D170001 p*q 77162EB107765764D2BE25B4A88CEB6954B18DBBFC72D868FC4EEBF000F01F1A9E06\ D72BFA3D95F6A629BFCE1F2CDF4809D987BF68196836469DC5FFDA88DA0900B8527D\ 869DCC9B4C7603CB7B50B60B0C1915A0E90C73F0ED72B5585C7BCC6DE5DA71841BBA\ DE3AA25110E0FA0E35BAC7D8BEB6DC58CDDE212631B6438E424739870E96026BB526\ DD027D6FE9EB392C09EA5AA9757DFFAB1C4EEE5B2852B160972E8BF77BB281CCFA56\ F7DE0903D4C43FDB7B339067DB6361A75E57B93B59E70D8FF7E6DA9A5FE0D31A4FB6\ 8E89859C4C99C85FBF5B83B2569D32ACEDF9EB0B0D34537340C87129B29E23D9A717\ 053D33A537D82087EEC7BE1C3F7CDEADBEEF (high order DEADBEEF) p = DEADBEEFB782E95FCB1B04C7A90F501FEC0F6FE8B5EDC31A0996DBF9CC088C7C07AE\ E9039616955FCEF1920730EE82B21E93B0E86A0160D2B3E0BDEF8B5E29BEC1D5A4CE\ F5E5F247B9765E05FE3BC285C485367CCE797FD244AC4B6AD3FCE4AFDFC93E3782F5\ AC11D9B541BD881BA35BF46F7E5DF5F996B681CF3D564B29F117 q = 123A78BC3DE4851ED3909CB37A402021766289052B9F7C9F00826E49117D\ C342EDAF5E4C6F7F76B54401C5F7AF599AA33EBBD76B07B50A89F38F8553CCEEF849\ B4B06A26F18095E82765930F119BFF11368A8D317B441C496E3B930356159AFD996A\ 86506614ECE175D8C28CF646BB4761F3F4340D64787118C1BF79 p*q DEADBEEFD6866764D5F0CE07C3303C39FF638B810AA7BFFF0C19F1F284056DB2A831\ D1BC4733564A17F19EEA00A332BCD7CA5A250206243A7FFF0DA0AE9E3407E3DD7AAE\ 7498860439CF8F59D14DA9D1AF1B1AC185AE55105A9FAA2FE5648B02F465BAEE244A\ 656D8AA4D5D5013C6AD3A8E91721387ED2AE77B53BA027560CF1A70937F3A3245C0F\ 59D7FE11D1FAD66BBC3AD3DC15B7F79C549E59C736E967724D2AAEA789552D28737E\ CEA5729860928BBA669BF249A9C266057DBCBC48A66C1B985AED8DF48B79F24A4740\ 62EECA3D844BBE7027BD80B9805CDD74CA760BDD16140277EDF792488CEB2F5FCBF9\ EF8D38E9769CD129AB97D542C3DBC0A1CDF --Anton - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Prime numbers guru 'factors' down success
- Original Message - From: Ben Laurie [EMAIL PROTECTED] To: William Knowles [EMAIL PROTECTED] Cc: [EMAIL PROTECTED] Sent: Monday, January 20, 2003 11:47 AM Subject: Re: Prime numbers guru 'factors' down success William Knowles wrote: Prime numbers (such as 1, 5, 11, 37...) are divisible only by themselves or 1. While smaller prime numbers are easy to make out, for very large numbers, there never had been a formula for primality testing until August 2002. Doh! This is so untrue. The point is that they discovered a test that wasn't NP, for the first time. OK, so its P but with a vast constant, but even so, there must be a point at which it gets better than the best NP methods. I wonder if anyone's worked out where that point is? Technically you can't say that. P is in NP, so if a problem is found to be in P, it's not out of NP. Note as well that the *problem* is situated in a complexity class, not the *algorithm* that solves it. It was known before Agrawal and al. result that primality testing was in ZPP for example (a class between P and NP). The following FAQ explains this in a bit more of detail: http://crypto.cs.mcgill.ca/~stiglic/PRIMES_P_FAQ.html But the core of Laurie's argument is correct, in that it's not true that only since Agrawal and al. result can we determine if large integers are primes or not, allowing for exponentially small probability of errors there are previously known algorithms that do much better than the algorithm from Agrawal and al. --Anton - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Micropayments, redux
Yes, but the probability of it being significantly worse than I claimed (i.e., by more than a factor t) is exponentially small (in t). One can easily calculate concretely exactly what the risk curve looks like. I'll spare everyone the details and just say that I see no reason why this should be a showstopper in practice. Actually I think it may be a showstopper in practice for rather different reasons -- people's behaviour when exposed to risks is rather odd. There is no risk for the user in the new schemes (which is what Peppercoin is developing)! Read the paper and/or presentation Zulfikar referenced in his post. The risk is for the Bank. --Anton - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Cryptographic privacy protection in TCPA
Nomen Nescio wrote: 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=PTO2Sect2=HITOFFp=1u=/ne tahtml/PTO/search-bool.htmlr=1f=Gl=50co1=ANDd=PG01s1=camenischOS=came nischRS=camenisch Jan Camenisch works for IBM, it's no surprise that the scheme is being patented. The scheme is not very efficient compared to Brands', but I would guess implementable if you don't mind doing allot of computation. It is based on zero-knowledge proofs. The basic idea of using zero-knowledge proofs to create an unlikable anonymous credentials system is actually pretty intuitive and simple, and people have taught about it before Camenisch Lysyanskay have. You can probably think about it yourself and come up with a similar scheme (not necessarily provably secure however) The novelty in my point of view is simply the choice of the setting in which they work in (group of quadratic residues modulo a composite), so that their scheme can apparently be proven secure under the strong RSA assumptions and the decisional DH assumption. Camenischs work on group signatures and Proving in zero-knowledge that a number n is the product of two safe primes seem to have lead to the result. --Anton - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
