Re: [cryptography] any info on (format-preserving) random permutation algorithms in java?
On 19/03/2013 00:50, travis+ml-rbcryptogra...@subspacefield.org wrote: > So, my problem is to create a format-preserving injective function > which is non-invertible (at least computationally). > > Since it's format preserving, it has to be a bijection, I'm guessing > that basically boils down to a (computationally strong?) random > permutation, for a domain of size =/= 2^n. A hash with n-bit result, with input domain restricted to n-bit, with n>=200 or so, is not a bijection, but is computationally indistinguishable from what Iunderstand is your requirement. Do I miss something?Or do you want it to be demonstrably format-preserving/bijective(rather than computationally indistinguishable from that)? http://crypto.stackexchange.com would be another nice place to ask. Francois Grieu ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] side channel analysis on phones
On 08/03/2013 14:11, Rob Kendrick wrote: >> 3. Timers on ARM chips don't have the same resolution as timers on x86 so >> cache based attacks are very possible but harder. > > The ARM has no timers as such; it's up to the SoC vendor to integrate > them. And some of them are very high resolution. At least some ARM cores have a System Timer, named SysTick http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.dai0179b/ar01s02s08.html Francois Grieu ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Intel RNG
d...@deadhat.com wrote: > CRI has published an independent review of the RNG behind the RdRand > instruction: > http://www.cryptography.com/public/pdf/Intel_TRNG_Report_20120312.pdf where *independent* is to be taken as per this quote: "This report was prepared by Cryptography Research, Inc. (CRI) under contract to Intel Corporation" Francois Grieu ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Proving knowledge of a message with a given SHA-1 without disclosing it?
On 01/02/2012 21:09, Jon Callas wrote: As I remember Hal's protocol, it requires about eight megabytes of data to be transferred back and forth to prove that you know the SHA1 hash. It's not so much to be obviously absurd, but not efficient enough to be something you'd want to do often. Close. If I get it correctly, it is a zero-knowledge proof, with one pass (leaving I guess <=50% odds of forgery) requiring 100 seconds and 22 kbytes of data (exchanged?), after some initial pre-computation requiring 40 minutes and 6MBytes of data (storage?), on a PC as it was circa 14 years ago. That, and more, is at 6'52" in the talk at http://video.google.com/videoplay?docid=-5745972992365920864 Hal Finney explains he got his result after careful optimizations, rewriting some SHA-1 internal operations as arithmetic operations in some appropriate field, rather than as boolean operations. Everything he says is convincing, but in 7 minutes there is not much detail, and so far I could not locate any later work (by him or others) claiming a comparable result. So it is hard to rule out that some error crept in his work. Francois Grieu ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Proving knowledge of a message with a given SHA-1 without disclosing it?
On 01/02/2012 18:50, Nico Williams wrote: On Wed, Feb 1, 2012 at 3:49 AM, Francois Grieu wrote: The talk does not give much details, and I failed to locate any article with a similar claim. I would find that result truly remarkable, and it is against my intuition. The video you posted does help me with the intuition problem. The idea seems to be to replace the normal arithmetic in SHA-1 with operations from a zero-knowledge scheme such that in the end you get a zero-knowledge proof of the operations that were applied to the input. That makes complete sense to me, even without seeing the details. But maybe I'm just gullible :^) Issues seem to be: can we chain commitments of commitments, to so many levels (hundreds, I guess), and still get something manageable? Did some detail slept in the talk's method? In particular, the XOR and ADD that make the bulk of SHA-1 are not field operations. A detailed analysis could tell, but we do not have enough detail on the talk's method, or on a similar claim. Francois Grieu ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Proving knowledge of a message with a given
Natanael wrote: > We do have zero-knowledge proofs, but AFAIK they do not use SHA1. I'm not after a proof that "uses" SHA-1; I'm after a proof of a message with given SHA-1 result, which is something very different. > http://en.wikipedia.org/wiki/Zero-knowledge_password_proof > http://en.wikipedia.org/wiki/Zero-knowledge_proof > http://en.wikipedia.org/wiki/Non-interactive_zero-knowledge_proof <-- > Most likely what you want Some of the techniques discussed here are close. In particular, some zero-knowledge proof of the solution of a SAT problem may fit the task, as it is easy to rewrite the problem h=SHA-1(m) for known h and unknown m as a SAT problem with some thousands clauses. However I'm afraid that the proof size (or the amount of work/data involved in the protocol) could grow beyond practicality. The talk does hint that it was necessary to use optimizations, but I could not extract enough information to understand which. Francois Grieu ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Proving knowledge of a message with a given SHA-1 without disclosing it?
On 01/02/2012 13:32, William Whyte wrote : > You can obviously prove it in the case where Alice claims she knows > SHA-1(SHA-1(m)), which seems to be the same claim. Alice discloses h and claims knowledge of m with h=SHA1(m). That's not equivalent to claiming knowledge of SHA-1(SHA-1(m)), which anyone can compute as SHA-1(h). Francois Grieu ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
[cryptography] Proving knowledge of a message with a given SHA-1 without disclosing it?
Alice discloses a 160-bit value h and claims that she (or parties/devices she has access to) knows a message m with h=SHA-1(m). Can she convince Bob of her claim using some protocol, without letting Bob find m, and without a third party or device that Bob trusts? At a Crypto'98 rump session, Hal Finney made a 7-minutes presentation "A zero-knowledge proof of possession of a pre-image of a SHA-1 hash" claiming a feasible protocol for this. http://video.google.com/videoplay?docid=-5745972992365920864 This talk mentions using the protocol in the Crypto'98 paper of Ronald Cramer and Ivan B. Damgård: "Zero-Knowledge Proofs for Finite Field Arithmetic or: Can Zero-Knowledge be for Free?" http://www.springerlink.com/content/0l4734h77615u161/ ftp://ftp.inf.ethz.ch/pub/crypto/publications/CraDam98.pdf http://www.brics.dk/RS/97/27/BRICS-RS-97-27.pdf The talk does not give much details, and I failed to locate any article with a similar claim. I would find that result truly remarkable, and it is against my intuition. Any info on the Hal Finney protocol, or a protocol giving a similar result, or the (in)feasibility of such a protocol? TIA, Francois Grieu ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Status of the Biryukov/Wagner slide attack against DESX?
On 2011-06-10 13:12, kg wrote at sci.crypt: > Francois Grieu wrote: >> I am reviewing the best known attacks against DESX. There is in >> particular A. Biryukov and D. Wagner: Advanced Slide Attacks, >> in the proceedings of Eurocrypt 2000 >> <http://www.iacr.org/archive/eurocrypt2000/1807/18070595-new.pdf> >> <http://www.cs.berkeley.edu/~daw/papers/advslide-ec00.ps> >> >> [...] >> >> DESX is defined from DES as >>DESXenc(, P) = E(K, P xor Kx) xor Ky = C >>DESXdec(, C) = D(K, C xor Ky) xor Kx = P >> where E is DES encryption and D is DES decryption. >> >> The attack as I read it at page 608 (14 in the PDF/PS) goes >> 1. Obtain 2^32.5 plain/ciphertext pairs >> 2. Enumerate the 2^56 DES keys K, and for each >> 3.- Compute each D(K, Ci) xor Pi and detect collisions >> 4.- For the few with D(K, Ci) xor Pi = D(K, Cj) xor Pj >> 5.-- Recover Ky = Ci xor Cj and Kx = Pi xor D(K, Ci xor Ky) >> [Note: the paper states Ky = Ci xor C'j] >> 6.-- Test that on a few plain/ciphertext pairs. >> >> I fail to see why at step 5. there would be a sizable chance that >> Ky = Ci xor Cj would recover the actual Ky, or what is meant in >> the paper by C'j and/or how to obtain it. > > I think the C'j is a typo, it should be Cj. > > > The argument should go as follows: In summary: I now get it fully, thanks to your excellent explanation! > (1) Among the observed plaintexts, the birthday paradox means that it > is likely that for some i != j, > > (*) Ci xor Cj = Ky. OK (with the the additional hypothesis that Ky!=0). [ I fail to derive that from the usual statement of the birthday paradox, but get something similar by considering F(i,j) = Ci xor Cj = E(K, Pi xor Kx) xor E(K, Pj xor Kx). F(i,j) is independent of Ky, and except for the fact that F(i,j) with i (2) If Ci xor Cj = Ky, then (see paper) > > (**) D(K,Ci) xor Pi = D(K,Cj) xor Pj. OK. I see how to derive that. If Ci xor Cj = Ky then D(K,Ci) = D(K, Ky xor Cj) = (D(K, Ky xor Cj) xor Kx) xor Kx = Pj xor Kx and similarly D(K,Cj) = Pi xor Kx hence (*) implies (**). > (3) For a given key K, we can compute D(K,Ci) xor Pi for all possible > i and look for collisions. This gives us pairs satisfying (**), but > perhaps not (*). OK. I now get it! > (4) If (**) holds for a pair and a key K, we can check if (*) > holds by computing Ky and Kx and checking these for a few other > plaintext-ciphertext pairs. > This seems to match the authors' claims. It does! >> Critically, I observe that the DES ciphertext fed into D at step 3 >> is mostly different from the DES ciphertext for actual >> plain/ciphertext pairs, unless of course Ky is 0; thus I fail to >> see how the detected collisions help. > > Most of the detected collisions do not help, but you notice that > they don't help when you get the wrong keys. OK. Even for the right K, it is possible that we get a false hit, but that would remain very marginal. Again, many thanks. Francois Grieu ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
[cryptography] Status of the Biryukov/Wagner slide attack against DESX?
Hello, I am reviewing the best known attacks against DESX. There is in particular A. Biryukov and D. Wagner: Advanced Slide Attacks, in the proceedings of Eurocrypt 2000 <http://www.iacr.org/archive/eurocrypt2000/1807/18070595-new.pdf> <http://www.cs.berkeley.edu/~daw/papers/advslide-ec00.ps> Among other results, this paper claims an attack against DESX with 2^32.5 plaintext/ciphertext pairs, 2^87.5 DES operations, and about 64 GiB of memory (I guess for each attack device). So far I had taken this peer-reviewed paper at face value, but I'm actually trying to dive into the details. And I fail to understand how the attack works! DESX is defined from DES as DESXenc(, P) = E(K, P xor Kx) xor Ky = C DESXdec(, C) = D(K, P xor Ky) xor Kx = P where E is DES encryption and D is DES decryption. The attack as I read it at page 608 (14 in the PDF/PS) goes 1. Obtain 2^32.5 plain/ciphertext pairs 2. Enumerate the 2^56 DES keys K, and for each 3.- Compute each D(K, Ci) xor Pi and detect collisions 4.- For the few with D(K, Ci) xor Pi = D(K, Cj) xor Pj 5.-- Recover Ky = Ci xor Cj and Kx = Pi xor D(K, Ci xor Ky) [Note: the paper states Ky = Ci xor C'j] 6.-- Test that on a few plain/ciphertext pairs. I fail to see why at step 5. there would be a sizable chance that Ky = Ci xor Cj would recover the actual Ky, or what is meant in the paper by C'j and/or how to obtain it. Critically, I observe that the DES ciphertext fed into D at step 3 is mostly different from the DES ciphertext for actual plain/ciphertext pairs, unless of course Ky is 0; thus I fail to see how the detected collisions help. Is anyone aware of a corrected version? Francois Grieu [posted at sci.crypt and cryptography mailing list @randombit.net] ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
[cryptography] Alleged recovery of PS3 ECDSA private key from signatures
According to a presentation made at the 27th Chaos Communication Congress, there is a serious bug in the code that was used to produce ECDSA signatures for the PS3: the same secret random was reused in several signatures, which allowed the team to recover the private key from signatures. The relevant part of the presentation starts at 5'15" in http://www.youtube.com/watch?v=84WI-jSgNMQ Francois Grieu ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
[cryptography] New result on MD5 collisions
There is a new result on MD5 collisions: it is feasible for 512 bit messages (instead of 1024 previously [*]) http://eprint.iacr.org/2010/643 Construct MD5 Collisions Using Just A Single Block Of Message Tao Xie and Dengguo Feng The example given is for the two distinct 64-byte messages 0e306561559aa787d00bc6f70bbdfe3404cf03659e704f8534c00ffb659c4c87 40cc942feb2da115a3f4155cbb8607497386656d7d1f34a42059d78f5a8dd1ef 0e306561559aa787d00bc6f70bbdfe3404cf03659e744f8534c00ffb659c4c87 40cc942feb2da115a3f415dcbb8607497386656d7d1f34a42059d78f5a8dd1ef which both hash to cee9a457e790cf20d4bdaa6d69f01e41 and differ in 2 bits only. The method is withheld for untold "security reasons", and a cash prize of $1 is announced for another example. The differential used was previously published in a paper by the same authors, but exploiting it was then an open problem. http://eprint.iacr.org/2009/223 Francois Grieu [*] the first collision published was in http://eprint.iacr.org/2004/199 Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD Xiaoyun Wang and Dengguo Feng and Xuejia Lai and Hongbo Yu exhibiting the two distinct 128-byte messages d131dd02c5e6eec4693d9a0698aff95c2fcab58712467eab4004583eb8fb7f89 55ad340609f4b30283e488832571415a085125e8f7cdc99fd91dbdf280373c5b 960b1dd1dc417b9ce4d897f45a6555d535739ac7f0ebfd0c3029f166d109b18f 75277f7930d55ceb22e8adba79cc155ced74cbdd5fc5d36db19b0ad835cca7e3 d131dd02c5e6eec4693d9a0698aff95c2fcab50712467eab4004583eb8fb7f89 55ad340609f4b30283e4888325f1415a085125e8f7cdc99fd91dbd7280373c5b 960b1dd1dc417b9ce4d897f45a6555d535739a47f0ebfd0c3029f166d109b18f 75277f7930d55ceb22e8adba794c155ced74cbdd5fc5d36db19b0a5835cca7e3 which both hash to a4c0d35c95a63a805915367dcfe6b751 and differ in 6 bits, 3 per 512-bit block, with the same locations/differential in each block. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Modern replacement for ANSI X9.31 as far as RSA key generation goes?
On 02/12/2010 18:33, I asked I'm in search for a current public standard (not necessarily free) specifying algorithms for RSA key generation, as a replacement for ANSI X9.31:1998; something with the range of the modulus and primes, and (mostly harmless and pointless) requirements on p-1, p+1, |p-q| and such, beside selecting random primes. Got it: FIPS 186-3 (issued June 2009), appendix B.3 http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf While not quite the same as ANSI X9.31:1998, it is similar enough that (unless I err) an RSA key generated according to FIPS 186-3 should *work* in an ANSI X9.31:1998 context, subject to only one restriction: the public modulus n has the appropriate bit size; in particular, the resulting bounds on p, q, and |p-q| are then exactly the same. Among the many differences that I spotted: FIPS 186-3 requires the public modulus n to be of k = 1024, 2048, or 3072 bits, while X9.31 allows k = 1024+256*s. FIPS 186-3 requires e to be odd from 17 to 160 bits, X9.31 allow e (including even) from 2 to k-160 bits. FIPS 186-3 allows random primes for p and q when k>=2048, while X9.31 always require safe primes. X9.31 requires that the auxiliary prime factors p1 of (p-1) and p2 of (p+1) be from 100 to 120 bits, whereas FIPS 186-3 specifies (when strong primes are used) a lower limit of 100, 140 or 170 bit depending on k, and defines an upper limit on the sum of the bit size of p1 and p2, depending both on k and whether p is a probable or provable prime (I wonder what the rationale for that upper limit is). Same for q. FIPS 186-3 requires a check that d (defined as the smallest valid private exponent) is more than k/2 bits, although this is acknowledged to be the case with high probability (I wonder what the rationale is). Francois Grieu ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Modern replacement for ANSI X9.31 as far as RSA key generation goes?
On 02/12/2010 18:46, Paul Rubin wrote: > Francois Grieu writes: >> I'm thus in search for a current public standard (not >> necessarily free) specifying algorithms for RSA key >> generation, as a replacement for ANSI X9.31:1998; > > Does IEEE 1363 have what you want? Upon checking, yes and that's a good idea. Thanks. I found a few issues though. One issue is that there is nothing prescribed in the body of the P1363 standard, but at least there is a SUGGESTION to use "A.16.11 An Algorithm for Generating RSA Keys" and that can be given as a reference. The worse is is that the factors generated per A.16.11 in P1363 do not seem guaranteed to be compatible with a gizmo working per ANSI X9.31:1998, for the former allows p and q to be of different bit size (and unless I err often does so), while the later prescribes primes of equal size. That could be a serious issue for CRT implementations of the private key function. Also ANSI X9.31:1998 has requirements for the bit size of e and n, that are not in P1363 as far as I see. Ahhh, standards, how to choose between them? Francois Grieu ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Modern replacement for ANSI X9.31 as far as RSA key generation goes?
ANSI X9.31:1988 is both shown as withdrawn and offered for sale at http://www.techstreet.com/standards/X9/X9_31_1998?product_id=1327214 Francois Grieu ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
[cryptography] Modern replacement for ANSI X9.31 as far as RSA key generation goes?
Hi, apparently, ANSI X9.31:1998 is no longer for sale. That's a sign that it is withdrawn (although I find no statement to that effect, and some recent FIPS documents that refer to it). I'm thus in search for a current public standard (not necessarily free) specifying algorithms for RSA key generation, as a replacement for ANSI X9.31:1998; something with the range of the modulus and primes, and (mostly harmless and pointless) requirements on p-1, p+1, |p-q| and such, beside selecting random primes. PKCS#1 v2.1 does not cut it; it defines valid keys, but not how to select the primes. ANSI X9.80:2005 does not seem to cut it (it is about random primes, not RSA keys). I suspect the same holds for ISO/IEC 18032:2005 Any pointer? TIA Francois Grieu ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] RSA question
[reposted with a correction, the log(2) factor] On 04/09/2010 15:07, victor.ducho...@morganstanley.com apparently wrote: > one could look-up the brute-force cost of RSA > vs. (ideal) symmetric algorithms, and discover that > while brute forcing an ideal symmetric algorithm doubles > in cost for every additional key bit, GNFS factoring cost > is approximately proportional to > > exp(n^(1/3)*log(n)^(2/3)) > > where "n" is the number of key bits. > No. According to sources such as <http://eprint.iacr.org/2010/006.pdf> the effort to factor a number n bits is approximately proportional to exp( (n*(log(2)*64/9+o(1)))^(1/3) * log(n*log(2))^(2/3) ) Any of the log(2), 64/9 and o(1) term change the effort estimate way more than by a constant factor. > So compared to 1k RSA bits, 16k RSA bits has a GNFS cost > that is (16*1.96)^(1/3) ~ 3.15 times higher. This is wrong well beyond the omission of the log(2)*64/9+o(1) term. By application of the above formula with n=16384 and n=1024, and expressing the ratio as a power of 2, I (now) get that the cost of factoring 16 kbits RSA numbers would be approximately 2^190 times that of factoring a 1 kbits RSA number if we neglect the o(1) term [and still 2^99 times, rather than 3.15 times, when omitting the (necessary) log(2)*64/9+o(1) term]. > If 1k RSA bits is comparable to 80 symmetric bits, then > 16k RSA bits is comparable to 80*3.15 or 252 bits. One can't multiply key bit size by ratio of effort; we must instead *add* the *logarithm* in base 2 of the ratio of effort. We get that 16k bits RSA would be comparable to 80+219 = 270 bits symmetric key if we neglect the o(1) term [80+114 = 179 bits when omitting the log(2)*64/9+o(1) term]. Francois Grieu [Wondering if the financial and engineering crisis may have to do with how *we* do math] ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] RSA question
On 04/09/2010 15:07, victor.ducho...@morganstanley.com apparently wrote : > one could look-up the brute-force cost of RSA > vs. (ideal) symmetric algorithms, and discover that > while brute forcing an ideal symmetric algorithm doubles > in cost for every additional key bit, GNFS factoring cost > is approximately proportional to > > exp(n^(1/3)*log(n)^(2/3)) > > where "n" is the number of key bits. > No. As far is known, the effort is approximately proportional to exp( (n*(64/9+o(1)))^(1/3) * log(n)^(2/3) ) Both the 64/9 and the o(1) term change the effort estimate way more than a constant factor. > So compared to 1k RSA bits, 16k RSA bits has a GNFS cost > that is (16*1.96)^(1/3) ~ 3.15 times higher. This is wrong well beyond the omission of the 64/9+o(1) term. By straight application of the above formula with n=16384 and n=1024, and expressing the ratio as the nearest power of 2, we get that the cost of factoring 16 kbits RSA numbers would be approximately 2^219 times that of factoring a 1 kbits RSA number if we neglect the o(1) term [and still 2^114 rather than 3.15 times neglecting the 64/9+o(1) term]. > If 1k RSA bits is comparable to 80 symmetric bits, then 16k RSA bits is comparable to 80*3.15 or 252 bits. One can't multiply key bit size by ratio of effort; we must instead *add* the *logarithm* in base 2 of the ratio of effort. We get that 16k bits RSA would be comparable to 80+219 = 299 bits symmetric key if we neglect the o(1) term [80+114 = 194 bits neglecting the 64/9+o(1) term]. Francois Grieu [Wondering if the crisis of financial institutions may have to do with how they do math] ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
