Re: [cryptography] Digital cash in the news...
Nicholas Bohm write: Now I find I can exchange a little over five bitcoins for a 50 Amazon gift certificate that Amazon seems happy to credit to my account. Danilo Gligoroski wrote: Your example is about two actors: Amazon and BitCoin, acting within small amounts of goods, services and issued currency. John Levine wrote: No, it's not. There's someone who will trade you Amazon gift certificates for bitcoins. snip Amazon neither buys nor sells bitcoins. Not (directly, yet), but for the end user who possess a bitcoin it appears as that. The concept of having several entities in the financial chain between the end consumer of the goods and the issuer of those goods is present in the human history for thousands of years. I see that those kind of financial chains are building around the concept of Bitcoin too. I still am not aware of anything you can actually buy for bitcoins (as opposed to trading them for various kinds of real and fake money) other than drugs. Insisting on the story that you can only buy drugs by bitcoins in my view is too harsh toward the concept of Bitcoin. Last week I was in Helsinki on a summer school for cloud computing and there a guy offered me to buy me a beer with his bitcoins. I do not have any Bitcoin (yet), but as time goes on, probably I will have one. CERTAINLY NOT FOR BUYING DRUGS, but because I want to see how that nice crypto design works and grows in practice. The allegations that the Bitcoins are tool for buying drugs will probably repel some potential Bitcoin owners and sadly will imprint them as a dangerous social group. To paraphrase Peter Gutmann from his post on this topic from last week: How about the allegations about The Bitcoin-based Child Porn Market and The al-Qaeda/Bitcoin Connection. Regards, Danilo! ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] sander ta-shma + bitcoin, b-money, hashcash (Re: Is BitCoin a triple entry system?)
On 2011-06-14 6:13 PM, Adam Back wrote: See also: Auditable Anonymous Electronic Cash by Tomas Sander and Amnon Ta-Shma in crypto 1998. http://www.math.tau.ac.il/~amnon/Papers/ST.crypto99.pdf Its basically the idea of using non-interactive zero knowlede proof of membership in a list of coins as an alternative to blinding. The interesting thing is then the bank doesnt need a private key and doesnt much need to be trusted. Anyone can audit the list of coins, it is published; same for double spend database. The ZKP is a representation problem (like Stefan Brands ecash/credentials). They use Merkle trees to improve the computation efficiency (reduce the size of the representation problems that have to be presented and verified). Like bitcoin it provides auditability, but better than bitcoin it provides cryptographically secure anonymity. With bitcoin it is not anonymous, just pseudonymous but traceable - because there is publicly auditable signature chain showing transfers between pseudonyms. Sander Ta-Shma propose using it with a physical bank providing exchange, but that could be replaced with variable cost hashcash like bitcoin. I dont understood why bitcoin didnt use it It is not a design, but an idea for a design. There is no efficient zero knowledge proof that has the required properties. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
[cryptography] GOST attack
http://eprint.iacr.org/2011/312.pdf: In this paper we show that GOST is NOT SECURE even against differential cryptanalysis (DC), or rather advanced attacks based on sets of differentials. [...] An Improved Differential Attack on GOST [...] Overall this attack requires 2^64 KP [known pairs, I guess] and allows to break full 32-round GOST in time of about 2^228 GOST encryptions for a success probability of 50 %. Since GOST has a 64-bit block size, it means that the attacker starts with the full map of (plaintext, ciphertext) pairs. In a sane system the key is either random or a result of KDF -- what can be the point of such an attack? -- Regards, ASK ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] GOST attack
AFAIU this attack indeed needs store all 2^64 plaintext/ciphertext pairs, and needs 2^228 computations. This makes it less interesting than a generic codebook attack, which only needs the former 2^64 storage. Saying GOST is NOT SECURE is thus exaggerated, to say the least... A far-fetched scenario where this attack may reduce security is one wherein the same 256b key is used for both GOST and (say) AES-256. Even in that case, it's not obvious that the said attack would be more efficient than a clever bruteforce. On Tue, Jun 14, 2011 at 1:25 PM, Alexander Klimov alser...@inbox.ru wrote: http://eprint.iacr.org/2011/312.pdf: In this paper we show that GOST is NOT SECURE even against differential cryptanalysis (DC), or rather advanced attacks based on sets of differentials. [...] An Improved Differential Attack on GOST [...] Overall this attack requires 2^64 KP [known pairs, I guess] and allows to break full 32-round GOST in time of about 2^228 GOST encryptions for a success probability of 50 %. Since GOST has a 64-bit block size, it means that the attacker starts with the full map of (plaintext, ciphertext) pairs. In a sane system the key is either random or a result of KDF -- what can be the point of such an attack? -- Regards, ASK ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Crypto-economics metadiscussion
On 14/06/11 2:31 AM, Marsh Ray wrote: I 'aint no self-appointed moderator of this list and I do find the subject of economics terribly interesting, but maybe it would make sense to willfully confine the scope of our discussion of Bitcoin and other virtual currencies to the crypto side of it. Crypto people spend all their lives learning theoretical crypto in groups like this. Then they go and apply their theoretical crypto out in the real world, and it bombs. Or worse: http://forum.bitcoin.org/index.php?topic=16457.0 In contrast, economists spend all their lives learning theoretical econ in other places. Then they go and apply their theoretical econ in the real world, and it bombs. (Que in links to IMF, WB, etc.) Everything that the econ people say is true, but they ain't gonna build it. Everything that the crypto people say is true, but people ain't gonna use it. How might there be a place where the knowledge can pass back and forth? Back in the halcyon days of DigiCash, Zooko and I used to run an informal thing called the Weber Economics Club. Us digital cash people would collect every Friday night in a cafe called the Weber, and there we'd spend about an hour or two talking through some particular economics concept. And especially how it applied to our world of digital cash. We were very aware that economics was key to our designs, then. I'm not saying this group can do that. But, to the extent that the ecogniscenti can influence the crypto people, something of value might come out. To the extent that the cryptoplumbers can build something of economic stability, some good might come out. On the other hand, talking just pure theory is fun too :) iang PS: I agree that talk about the housing crisis belongs elsewhere. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] New bit-fiddling instructions in Intel's Haswell
On 14-06-2011 13:13, Jack Lloyd wrote: Intel has publicly described the new instructions that will be available in Haswell (their 22nm chip with ETA 2013). It will include integer AVX, and some interesting new bit fiddling instructions for GPRs, including bit-level gather/scatter instructions (pext/pdep), and an unsigned multiply instruction that doesn't set flags which seems intended for modexp. I suspect there are some interesting possibilities with pext/pdep. While it's about 15 years too late to matter, a table-less DES running entirely in registers seems possible. And last year I played around with a Serpent implementation using pshufb for the 4-bit sboxes, but couldn't find a way of doing the linear transformation quickly; doing the sboxes in the xmm registers and the linear operation in GPRs with these might work out, though. Anyone see other ways to use the new instructions in interesting ways, cryptographically speaking? The instruction reference (PDF) is posted on their formum: http://software.intel.com/en-us/forums/showthread.php?t=83399 -Jack ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography I'm actually unhappy that VPSHUFB still doesn't allow 32-byte wide shuffles (each half does its own 16-byte shuffle. It would seem Intel is still unwilling to abandon their 128-bit wide microarchitecture just yet...I'd very much like that Intel adopt the far more powerful PPERM instruction, part of AMD's XOP extensions. It would allow for 6-bit table lookups, which would even allow for AES bruteforce table lookups in a reasonable amount of cycles. The new integer shift instructions are, of course, interesting (I thought to have seen a rotation instruction in there, but apparently it was wishful thinking). Since every shift constant is variable, it allows for faster Salsa20/ChaCha20, but also speeds Threefish/Skein up by performing the various MIX rounds simultaneously. I can see the bit permutation instructions being used to do very fast binary field squaring (a linear operation) --- will probably be much faster than recurring to PCMULCLDQ, which is not too fast (in current hardware, at least). The Post-32nm instructions also contain RDRAND, which gives access to a hardware random bit generator. It would be interesting to see how these bits are being generated. Best regards, Samuel Neves ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Crypto-economics metadiscussion
On 15/06/11 12:47 AM, Ian G wrote: Or worse: http://forum.bitcoin.org/index.php?topic=16457.0 That link is down, no surprise. From my cached copy, I wrote it up on the blog: http://financialcryptography.com/mt/archives/001327.html Far too much from me, signing out... iang. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] GOST attack
On Tue, Jun 14, 2011 at 7:31 AM, Jean-Philippe Aumasson jeanphilippe.aumas...@gmail.com wrote: AFAIU this attack indeed needs store all 2^64 plaintext/ciphertext pairs, and needs 2^228 computations. This makes it less interesting than a generic codebook attack, which only needs the former 2^64 storage. Saying GOST is NOT SECURE is thus exaggerated, to say the least... A far-fetched scenario where this attack may reduce security is one wherein the same 256b key is used for both GOST and (say) AES-256. Even in that case, it's not obvious that the said attack would be more efficient than a clever bruteforce. It is not reasonable to consider an attack with a 2^228 work factor as breaking a cipher, nor is it reasonable to say that because this 2^28 times faster than a brute force attack that this is a break (also, the 2^64 storage requirement means that this attack is only ~2^23 times faster than brute force, because the random access to that storage won't be free). Perhaps that's a typo and the author meant 2^28? *That* would be a break, even with a 2^64 storage requirement. But skimming the paper it does not seem to be a typo. For me the problem with GOST is its block size. I would much prefer a 128-bit block size for reasons having to do with re-key considerations. Nico -- ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] GOST attack
To extract the essence of both Klimov's and Aumasson's posts about this attack from the codebook point of view (where I completely agree): Alexander Klimov alser...@inbox.ru wrote: Since GOST has a 64-bit block size, it means that the attacker starts with the full map of (plaintext, ciphertext) pairs. In a sane system the key is either random or a result of KDF -- what can be the point of such an attack? Jean-Philippe Aumasson wrote: AFAIU this attack indeed needs store all 2^64 plaintext/ciphertext pairs, and needs 2^228 computations. This makes it less interesting than a generic codebook attack, which only needs the former 2^64 storage. To illustrate the futility of this attack here is an extreme example with a baby-block, giant-key block cipher: Let we have a 4-bit block cipher with 256-bit keys. Give to the attacker all 2^4=16 pairs of (Plaintext, Ciphertext) i.e. give him the secret permutation of 16 elements that is our 4-bit block cipher with 256-bit key. Although mathematically is not equivalent as knowing the secret key, (in this case many different key values will give the same block cipher), for all cryptographic purposes (encryption, decryption, any mode of operation, producing MACs, ...) his knowledge of the full codebook will reproduce the same results as knowing one secret key. Now, 64-bit blocks are much bigger than 4-bit blocks, (and the secret key is still 256 bits i.e. much larger than the block size), but the principles of the codebook attack are the same. Thus the task of reproducing the secret key by knowing the full codebook of 2^64 pairs of (Plaintext, Ciphertext) after 2^228 computations is futile. Regards, Danilo! ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Oddity in common bcrypt implementation
On Tue, Jun 14, 2011 at 04:52:30PM -0500, Marsh Ray wrote: The first 7 chars $2a$05$ are a configuration string. The subsequent 53 characters (in theory) contains a 128 bit salt and a 192 bit hash value. But 53 is an odd length (literally!) for a base64 string, as base64 uses four characters to encode three bytes. I don't see an official reference for the format of bcrypt hashes. There's the Usenix 99 paper, which is a great read in many ways, but it's not a rigorous implementation spec. I discovered this a while back when I wrote a bcrypt implementation. Unfortunately the only real specification seems to be 'what the OpenBSD implementation does'. And the OpenBSD implementation also does this trunction, which you can see in ftp://ftp.fr.openbsd.org/pub/OpenBSD/src/lib/libc/crypt/bcrypt.c with encode_base64((u_int8_t *) encrypted + strlen(encrypted), ciphertext, 4 * BCRYPT_BLOCKS - 1); Niels Provos is probably the only reliable source as to why this truncation was done though I assume it was some attempt to minimize padding bits or reduce the hash size. -Jack ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Oddity in common bcrypt implementation
Also a discussion on this going on at http://news.ycombinator.com/item?id=2654586 On 06/14/2011 05:50 PM, Jack Lloyd wrote: I discovered this a while back when I wrote a bcrypt implementation. Unfortunately the only real specification seems to be 'what the OpenBSD implementation does'. That is something of a drawback to bcrypt. And the OpenBSD implementation also does this trunction, which you can see in ftp://ftp.fr.openbsd.org/pub/OpenBSD/src/lib/libc/crypt/bcrypt.c with encode_base64((u_int8_t *) encrypted + strlen(encrypted), ciphertext, 4 * BCRYPT_BLOCKS - 1); Niels Provos is probably the only reliable source as to why this truncation was done though I assume it was some attempt to minimize padding bits or reduce the hash size. That's a pretty weird design decision to use this massive 128 bit salt but then chop bits off the actual hash value to adjust the length. The 128 bit salt wastes 4 bits in the base64 encoding (22 chars * 6 bits per char = 132 bits). The 31 character base64 discards 8 of the 192 bit output bits (31*6 = 186). If they'd just used only a 126 bit salt they could base64 encode it in 21 chars with no wasted space. That would allow them to store the full 192 bits in 32 chars with no wasted space. So they threw away 8 hash output bits in order to save 2 salt bits. - Marsh ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Oddity in common bcrypt implementation
On Tue, Jun 14, 2011 at 06:50:18PM -0400, Jack Lloyd wrote: encode_base64((u_int8_t *) encrypted + strlen(encrypted), ciphertext, 4 * BCRYPT_BLOCKS - 1); Here's the commit by Niels that fixes the bug in encode_base64() and replaces it with the explicit - 1 above: http://www.openbsd.org/cgi-bin/cvsweb/src/lib/libc/crypt/bcrypt.c.diff?r1=1.11;r2=1.12 That was in 1998. The commit message not surprisingly says: fix base64 encoding, this problem was reported by Solar Designer so...@false.com some time ago. So it was indeed a deliberate decision not to break compatibility, which made sense to me. Who cares if it's 192 or 184 bits, as long as we all agree on a specific number. Using base-64 more optimally could be nice, but not enough of a reason to break compatibility either. And, by the way, it's not base64, but just a base 64 encoding. It can produce any number of characters, not just multiples of 4. By the way, it is also subtly incompatible with the base 64 encoding used by other common crypt(3) implementations... which is not base64 either. In this posting, I am using base64 (without the dash) to refer to base64 as in MIME, and base-64 (with the dash) to other base 64 encodings (which vary). Alexander ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] GOST attack
On Tue, Jun 14, 2011 at 7:25 PM, Alexander Klimov alser...@inbox.ru wrote: http://eprint.iacr.org/2011/312.pdf: Overall this attack requires 2^64 KP [known pairs, I guess] and allows to break full 32-round GOST in time of about 2^228 GOST encryptions for a success probability of 50 %. Since GOST has a 64-bit block size, it means that the attacker starts with the full map of (plaintext, ciphertext) pairs. In a sane system the key is either random or a result of KDF -- what can be the point of such an attack? I do not think there is any point at all. 2^64 known pairs is a complete codebook, which in itself breaks the cipher. The attacker can just look up any future ciphertext block in the book and recover the plaintext. Game over. Even in theory, an attack that requires 2^keysize or more encryptions is uninteresting because a brute force attack is simpler. Similarly, one that requires 2^blocksize or more blocks of known plaintext is uninteresting because the codebook attack is simple and effective. In practice, there are other problems. The attacker needs storage for 2^64 blocks, and the attack only works if the cipher is not rekeyed in that volume of data. This is not even close to a practical attack. The only way this paper could become interesting is if, as the authors suggest, it is only a first step toward better attacks. Wait and see. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] sander ta-shma + bitcoin, b-money, hashcash (Re: Is BitCoin a triple entry system?)
On 2011-06-15 1:29 AM, Ian G wrote: Which, to my mind was the same sin as the alternate: obsession with privacy, including to the extent of eliminating the core requirements of money. The first law of money is that it has to be safe: http://forum.bitcoin.org/index.php?topic=16457.0 This is the fundamental reason why we have reversable transactions in systems to account for money ... (whatever we think of the result, there is a reason why we have that feature). This is also why nymous (public-key identified) transaction systems will always beat out coin-based (blinded) systems in the long run. This seems inconsistent with the May scale of monetary hardness, and the ancient appeal of gold money. Reversible (soft) money has to have at its foundation irreversible and final hard money. Thus, in the days of the gold standard, all the banks would do final settlement in gold, and people tended to pay in banknotes. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Digital cash in the news...
On 2011-06-15 7:58 AM, Nico Williams wrote: Let's say you have an unbreakable code. Which we do. But there's still traffic analysis, and even with onion routing and such, you don't know if your peers are ratting you out, If one of the mixers is my own, I know that that mixer is not ratting me out. One valid mixer in the chain is sufficient to be a serious obstacle to the state. Two is very serious obstacle. And chances are that both I and the guy I am talking to are running our own mixers. Do the same thought experiment regarding cryptographic coins if you like. The state could easily make it so insignificant amounts of business gets transacted in a cryptographic coin that the state cannot subvert or control. I observe that a large part of the world's economy is run though virtual private networks running through tax haven islands. Looks to me that the horse is already bolting. Wealthy individuals and big corporations use transferable promises to pay by other wealthy individuals transferred over video conference as money, which hawala like money is difficult or impossible for the state to track. So for the very rich, particularly wealthy Chinese businessmen located outside of China, the cypherpunk program is becoming real. Unfortunately, it is not becoming real for cypherpunks, who hoped that the white middle class would get in on it. But *some* people are getting in on it. Chinese are respectful of authority, and superficially compliant, but they have a long history of quiet evasion and subtle resistance, so are naturally inclined to cypherpunkish solutions. The growth of China is in substantial part the growth of the economy mediated by virtual private networks. Much of the Chinese economy, notably real estate development and mining, is transparent to the state and run by companies that legally Chinese, and Chinese in reality, but much of the Chinese economy, notably hi tech, is run by companies that are not legally Chinese, indeed their location is hard to find. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
