Re: anonymous DH MITM
bear wrote: On Fri, 3 Oct 2003, Benja Fallenstein wrote: bear wrote: Why should this not be applicable to chess? There's nothing to prevent the two contestants from making nonce transmissions twice a move when it's not their turn. I.e., you would need a protocol extension to verify the nonces somehow-- if that's possible at all-- or are you just faster than me, and have thought about a way to do that already? Not faster per se, but I do happen to know the solution to that problem. :-) Ah, good ;-) Suppose Alice picks a nonce A(zero). Then for n=one to a thousand (presumably no chess game will last 1000 moves) she calculates A(n) = hash (A(n-1)). Does it work? Assume A() is Alice's series, B() is Bob's, MA() is the one Mitch uses with Alice, MB() the one Mitch uses with Bob. - Mitch sends first half of cyphertext of MA(1000) (to Alice) - Alice sends first half of cyphertext of her move + A(1000) (to Mitch) - Mitch sends second half - Alice sends second half Mitch can now decrypt Alice's move. - Bob sends first half of cyphertext of B(1000) (to Mitch) - Mitch sends first half of cyphertext of Alice's move + MB(1000) (to Bob) - Bob sends second half. - Mitch sends second half. Bob decides on his move. - Bob sends first half of ciphertext of his move + B(999) (to Mitch) - Mitch sends first half of ciphertext of MB(999) (to Bob) - Bob sends second half. - Mitch sends second half. Mitch can now decrypt Bob's move... Am I missing something? - Benja - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: anonymous DH MITM
Hi, bear wrote: starting with Rivest Shamir's Interlock Protocol from 1984. Hmmm. I'll go read, and thanks for the pointer. Perhaps I spoke too soon? It's not in Eurocrypt or Crypto 84 or 85, which are on my shelf. Where was it published? Communications of the ACM: Rivest and Shamir, How to expose an eavesdropper, CACM vol 24 issue 4, 1984. If you have an ACM Digital Library account, it's at http://portal.acm.org/ft_gateway.cfm?id=358053type=pdfcoll=ACMdl=ACMCFID=12683735CFTOKEN=40809148 I've started writing a short summary earlier today, after reading, but then I got distracted and didn't have time... sorry :) Hope this helps anyway. The basic idea is that Alice sends *half* of her ciphertext, then Bob *half* of his, then Alice sends the other half and Bob sends the other half (each step is started only after the previous one was completed). The point is that having only half of the first ciphertext, Mitch can't decrypt it, and thus not pass on the correct thing to Bob in the first step and to Alice in the second, so both can actually be sure to have the public key of the person that made the other move. - Benja - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: anonymous DH MITM
Hi -- bear wrote: On Thu, 2 Oct 2003, Zooko O'Whielacronx wrote: R. L. Rivest and A. Shamir. How to expose an eavesdropper. Communications of the ACM, 27:393-395, April 1984. Ah. Interesting, I see. It's an interesting application of a bit-commitment scheme. Ok, so my other mail came far too late to be useful to you ;-) Why should this not be applicable to chess? There's nothing to prevent the two contestants from making nonce transmissions twice a move when it's not their turn. Maybe you have already a more advanced thing in mind than I do, but if your protocol would then look just like this-- - Alice sends first half of cyphertext of her move - Bob sends first half of cyphertext of random nonce - Alice sends second half - Bob sends second half and vice versa, consider this: - Alice sends first half of cyphertext of her move (to Mitch) - Mitch sends first half of cyphertext of random nonce (to Alice) - Alice sends second half - Mitch sends second half - Mitch sends first half of cyphertext of Alice's move (to Bob) - Bob sends first half of cyphertext of random nonce (to Alice) ... I.e., you would need a protocol extension to verify the nonces somehow-- if that's possible at all-- or are you just faster than me, and have thought about a way to do that already? Thx, - Benja - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Literature about Merkle hash tries?
Hi all, Does anybody on this list know literature about cryptographic hash tries? (I hit on this idea when mulling about a different problem, and was wondering what people have written about it.) I.e., a data structure for keeping sets of pieces of data, by: - computing a cryptographic hash of each piece, treating each hash as a bitstring; - organizing these in a trie (A tree for storing strings in which there is one node for every common prefix. The strings are stored in extra leaf nodes, http://www.nist.gov/dads/HTML/trie.html); - treating this trie as a Merkle hash tree. For example, if we have four hashes starting [0001], [0010], [1110] and [] respectively, :: [root] / \ [0] [1] / \ [00] [11] / \ \ 0001.. 0010.. [111] / \ 1110.. .. The nodes with one child can also be omitted for efficiency, i.e.:: [root] / \ /\ / \ [00] \ / \ \ 0001.. 0010.. [111] / \ 1110.. .. This could easily be extended to provide a mapping, by treating the keys as above, and putting each values in the extra leaf node of their corresponding key. It seems to me that this data structure would-- - allow giving efficient proofs not only of membership, but also non-membership, by giving the path through the tree that would end up at that item, but show that it ends up at a different item. E.g., to prove that a hash starting [0011] is not in the above set, give the path to 0010... (This could be used to implement CRTs.) - be automatically approximately balanced (I haven't attempted a proof, but since all prefixes are conjectured to be equally likely...) - allow you to maintain a history of such trees with only O(log n) additional storage cost per addition or removal-- i.e., if you already have a whole tree with n items, and want to additionally store a tree that has one item added, you only need O(log n) additional storage space-- and you don't need to implement some complicated re-balancing algorithm (if the previous conjecture holds). It's functionally equivalent to having a binary search tree that stores a value at each internal node, but it seems potentially simpler to implement, particularly when you want to store a versioned history (e.g. of a CRT), because you don't need to implement re-balancing. So, anyway, anybody know references? I've not come across any yet. Thanks, - Benja - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Literature about Merkle hash tries?
Hi Greg-- Greg Rose wrote: At 01:14 AM 10/1/2003 +0300, Benja Fallenstein wrote: So, anyway, anybody know references? I've not come across any yet. I know that the technique dates back (at least) to IBM in the 60s. Cool-- but-- On second thoughts, do you mean *cryptographic* hash tries or hash tries or plain tries? I know literature on both tries and hash tries (Knuth claimed to have invented the latter in an Literate Programming exercise) but not on using cryptographic hash functions a Merkle hash tree. Reason for my second thoughts is that Merkle's patent on hash trees dates in the 80s ;-) I used to know the name of the inventor but can't bring it to mind at the moment. The Berkeley UNIX library dbm uses essentially this philosophy, but the tree is not binary; rather each node stores up to one disk block's worth of pointers. Nodes split when they get too full. When the point is to handle a lot of data, this makes much more sense. (In Merkle hash trees, on the other hand, signature size is minimized when using a binary tree, at least if I'm not confused right now. :) ) Thanks, - Benja - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
