5 ms·

Single-prime RSA is commutative. Agree on prime p, and encrypt with random prime e. d = e^-1 (mod p-1) which is easy to calculate using Extended Euclidean Algor

by fryguy 12y ago

Single-prime RSA is commutative. Agree on prime p, and encrypt with random prime e. d = e^-1 (mod p-1) which is easy to calculate using Extended Euclidean Algorithm. With keys e and r, (m^e)^r === m^er === m^re === (m^r)^e (mod p).

stouset 12y ago
Asymmetric cryptography isn't necessary here, and is typically much slower and much more complicated. Any stream cipher (e.g., AES-CTR) XORs a keystream against the plaintext. XOR is trivially commutative. Players would have to commit to their keys ahead of time, however (one approach is to publish a hash of the key). Otherwise, a player can cheat by enumerating keys at random until they find one that causes the deck to decrypt to a more favorable ordering.
- fryguy 12y ago
  You don't really even need a stream cipher, just random data if you're using XOR. You're right that XOR is trivially commutative, but it is weak to known-plaintext attacks which makes it unsuitable for this algorithm. Suppose you have a deck { 1, 2, 3, 4 }, I'm alice(A) and you're bob(B) and I'll denote xor with dot. I shuffle it with the first round, revealing { A(3), A(1), A(2), A(4) } and then you shuffle revealing { B.A(2), B.A(4), B.A(3), B.A(1) } Then we re-encrypt with unique keys: { A_1.B(2), A_2.B(4), A_3.B(3), A_4.B(1) } { A_1.B_1(2), A_2.B_2(4), A_3.B_3(3), A_4.B_4(1) } Now you "deal" me the first card by revealing B_1. This means that I know that the first slot is card 2. But I also know `B xor A xor 2` from the end of the first phase, which means it's easy to calculate what `B xor A` is. From this, I can decrypt the entire deck.
  - stouset 12y ago
    When I mentioned the use of a stream cipher, I assumed that either different parts of the keystream or an entirely new keystream from a unique nonce would be used to encrypt each separate card. Encrypting multiple values with the same key and initialization vector (or the same key and no IV) is usually a bad idea no matter the scenario. Assuming Alice has secret keys k_{a1}, k_{a2} and Bob has secrets keys k_{b1}, k_{b2}: # unshuffled deck deck = { 1, 2, 3, 4 } # alice shuffles the deck, encrypts with and commits # to k_a1 deck_{a1} = { 3 ^ E(k_{a1}, 0), # card 3 1 ^ E(k_{a1}, 1), # card 1 2 ^ E(k_{a1}, 2), # card 2 4 ^ E(k_{a1}, 3) # card 4 } # bob shuffles the deck, encrypts with and commits to # k_b1 deck_{a1,b1} = { 1 ^ E(k_{a1}, 1) ^ E(k_{b1}, 0), # card 1 4 ^ E(k_{a1}, 3) ^ E(k_{b1}, 2), # card 4 2 ^ E(k_{a1}, 2) ^ E(k_{b1}, 1), # card 2 3 ^ E(k_{a1}, 0) ^ E(k_{b1}, 3) # card 3 } # alice removes her first layer of encryption and # reencrypts with k_a2 and a secret random IV for # each card deck_{a2,b1} = { 1 ^ E(k_{a2}, 0x2a94aebde) ^ E(k_{b1}, 0), # card 1 4 ^ E(k_{a2}, 0xcb4129ac4) ^ E(k_{b1}, 2), # card 4 2 ^ E(k_{a2}, 0x3521d1946) ^ E(k_{b1}, 1), # card 2 3 ^ E(k_{a2}, 0x18e43069d) ^ E(k_{b1}, 3) # card 3 } # bob removes his first layer of encryption and # reencrypts with k_b2 and a secret random IV for # each card deck_{a2,b2} = { 1 ^ E(k_{a2}, 0x2a94aebde) ^ E(k_{b2}, 0x559ff441), # card 1 4 ^ E(k_{a2}, 0xcb4129ac4) ^ E(k_{b2}, 0x80549428), # card 4 2 ^ E(k_{a2}, 0x3521d1946) ^ E(k_{b2}, 0x344c2f79), # card 2 3 ^ E(k_{a2}, 0x18e43069d) ^ E(k_{b2}, 0x306a4732) # card 3 } When cards are dealt and decrypted, nothing is leaked about the other cards. Again, you still need parties to commit to their keys when publishing the shuffled deck, but that is likely a requirement of other implementations too — the attack is simply more obvious when using a stream cipher due to the ease of malleability. Generating an authenticator the deck ciphertext at each step is probably also a reasonable idea, but I haven't given it much thought. This is supposed to be an illustrative example (e.g., random IVs would need to be much larger than 32 bits).
    - fryguy 12y ago
      to go from deck_{a1,b1} to deck_{a2,b1} you need to remove the encryption. In order to remove E(k_{a1}, ?), you need to know which one was used, but can't, because it was shuffled. If you were able to know which one was used, you would know which card it was.

by fryguy 12y ago

stouset 12y ago

Asymmetric cryptography isn't necessary here, and is typically much slower and much more complicated. Any stream cipher (e.g., AES-CTR) XORs a keystream against the plaintext. XOR is trivially commutative. Players would have to commit to their keys ahead of time, however (one approach is to publish a hash of the key). Otherwise, a player can cheat by enumerating keys at random until they find one that causes the deck to decrypt to a more favorable ordering.

fryguy 12y ago
You don't really even need a stream cipher, just random data if you're using XOR. You're right that XOR is trivially commutative, but it is weak to known-plaintext attacks which makes it unsuitable for this algorithm. Suppose you have a deck { 1, 2, 3, 4 }, I'm alice(A) and you're bob(B) and I'll denote xor with dot. I shuffle it with the first round, revealing { A(3), A(1), A(2), A(4) } and then you shuffle revealing { B.A(2), B.A(4), B.A(3), B.A(1) } Then we re-encrypt with unique keys: { A_1.B(2), A_2.B(4), A_3.B(3), A_4.B(1) } { A_1.B_1(2), A_2.B_2(4), A_3.B_3(3), A_4.B_4(1) } Now you "deal" me the first card by revealing B_1. This means that I know that the first slot is card 2. But I also know `B xor A xor 2` from the end of the first phase, which means it's easy to calculate what `B xor A` is. From this, I can decrypt the entire deck.
- stouset 12y ago
  When I mentioned the use of a stream cipher, I assumed that either different parts of the keystream or an entirely new keystream from a unique nonce would be used to encrypt each separate card. Encrypting multiple values with the same key and initialization vector (or the same key and no IV) is usually a bad idea no matter the scenario. Assuming Alice has secret keys k_{a1}, k_{a2} and Bob has secrets keys k_{b1}, k_{b2}: # unshuffled deck deck = { 1, 2, 3, 4 } # alice shuffles the deck, encrypts with and commits # to k_a1 deck_{a1} = { 3 ^ E(k_{a1}, 0), # card 3 1 ^ E(k_{a1}, 1), # card 1 2 ^ E(k_{a1}, 2), # card 2 4 ^ E(k_{a1}, 3) # card 4 } # bob shuffles the deck, encrypts with and commits to # k_b1 deck_{a1,b1} = { 1 ^ E(k_{a1}, 1) ^ E(k_{b1}, 0), # card 1 4 ^ E(k_{a1}, 3) ^ E(k_{b1}, 2), # card 4 2 ^ E(k_{a1}, 2) ^ E(k_{b1}, 1), # card 2 3 ^ E(k_{a1}, 0) ^ E(k_{b1}, 3) # card 3 } # alice removes her first layer of encryption and # reencrypts with k_a2 and a secret random IV for # each card deck_{a2,b1} = { 1 ^ E(k_{a2}, 0x2a94aebde) ^ E(k_{b1}, 0), # card 1 4 ^ E(k_{a2}, 0xcb4129ac4) ^ E(k_{b1}, 2), # card 4 2 ^ E(k_{a2}, 0x3521d1946) ^ E(k_{b1}, 1), # card 2 3 ^ E(k_{a2}, 0x18e43069d) ^ E(k_{b1}, 3) # card 3 } # bob removes his first layer of encryption and # reencrypts with k_b2 and a secret random IV for # each card deck_{a2,b2} = { 1 ^ E(k_{a2}, 0x2a94aebde) ^ E(k_{b2}, 0x559ff441), # card 1 4 ^ E(k_{a2}, 0xcb4129ac4) ^ E(k_{b2}, 0x80549428), # card 4 2 ^ E(k_{a2}, 0x3521d1946) ^ E(k_{b2}, 0x344c2f79), # card 2 3 ^ E(k_{a2}, 0x18e43069d) ^ E(k_{b2}, 0x306a4732) # card 3 } When cards are dealt and decrypted, nothing is leaked about the other cards. Again, you still need parties to commit to their keys when publishing the shuffled deck, but that is likely a requirement of other implementations too — the attack is simply more obvious when using a stream cipher due to the ease of malleability. Generating an authenticator the deck ciphertext at each step is probably also a reasonable idea, but I haven't given it much thought. This is supposed to be an illustrative example (e.g., random IVs would need to be much larger than 32 bits).
  - fryguy 12y ago
    to go from deck_{a1,b1} to deck_{a2,b1} you need to remove the encryption. In order to remove E(k_{a1}, ?), you need to know which one was used, but can't, because it was shuffled. If you were able to know which one was used, you would know which card it was.