Problem C
Key Exchange
Key exchange is a protocol for securely sharing cryptographic keys so that communicators may proceed with encrypted communications. The idea is to share the key in such a way that it is impossible (or at least computationally infeasible) for an adversary to figure out what the key is. Computer security professionals regulary have to design and evaluate computer security protocols. Here’s an example of a hypothetical key exchange protocol that tries to hide the key in a data file in such a way that it is very hard to find. Your task is to peform the role of a computer security analyst and prove the key is actually pretty easy to find if the protocol is weak.
The key exchange protocol involves sending a $10$kb data file in which the key is hidden. The seemingly random data in the file contains two disjoint same-length sequences $S$ and $T$ of consecutive bytes, where $T$ is a permutation of $S$. That is, $T$ has the very same bytes as $S$, but in a different order. The protocol allows for any key length between $64$ and $256$ bytes, inclusive, and the length of the key must be inferred from the file. If we can discover $S$ and $T$, the decryption key is merely the bytewise XOR of these sequences–you won’t be asked to compute that, but only to find $S$ and $T$.
Input
The input is a single line of at least $128$b and up to $10$kb of data, represented as a comma-delimited list of bytes (integers between $0$ and $255$ inclusive). Note that the input might contain newlines or other whitespace between bytes in addition to the commas.
Output
Print three integers: the length of the key in bytes, the (0-based) index of the first byte in $S$ in the input data, and the index of the first byte of $T$ in the data. If there are multiple possible key pairs satisfying the constraints described above, print the information for the pair with longest length; break further ties by smallest value of index of the first byte in $S$ and then smallest value of the index of the first byte of $T$. If there isn’t any possible key hidden in the file, print no key.
Sample Input 1 | Sample Output 1 |
---|---|
1,34,179,143,84,209,106,218,157,1,46,246,83,186,237,73,190, 239,118,154,190,208,189,131,131,179,110,36,124,143,15,91, 252,47,199,150,82,121,112,205,56,99,84,214,97,96,220,141, 117,250,116,225,147,57,13,121,73,222,173,76,184,199,74,210, 169,150,57,156,61,151,223,95,95,225,219,18,245,77,229,78, 204,200,170,144,118,237,143,220,74,116,250,210,73,124,56, 106,84,141,1,91,199,169,214,246,76,208,186,190,47,156,57, 117,184,121,73,205,112,82,84,131,199,15,173,225,222,179,190, 83,150,239,99,57,110,121,13,36,209,131,154,218,147,252,97, 61,46,157,150,96,189,50,241,118,150,78,61,240,64,59,30,48 |
65 4 84 |
Sample Input 2 | Sample Output 2 |
---|---|
34,65,161,36,36,180,198,146,209,180,177,16,203,63, 177,63,121,248,138,196,100,128,209,157,45,59,234, 146,5,43,180,159,94,53,144,182,194,155,9,129,183, 5,159,255,124,42,247,145,13,9,251,109,203,252,154, 195,73,6,212,155,36,175,95,29,84,23,220,166,239, 203,223,101,88,171,70,103,43,116,124,194,105,204, 121,57,141,98,115,147,81,163,27,83,248,101,100, 239,23,166,223,6,129,124,121,43,146,105,220,5,42, 154,98,95,194,204,145,59,5,155,13,73,247,88,171, 43,109,195,9,157,124,57,45,94,155,251,53,36,70, 159,180,203,203,159,182,103,128,29,183,255,252, 194,9,84,234,212,209,144,141,175,116,193,61,178, 10,192,218,71,90,75,113,84,93,125,232,67,169,120, 129,253,78,76 |
66 20 93 |
Sample Input 3 | Sample Output 3 |
---|---|
69,216,4,64,16,167,134,229,46,227, 208,148,41,166,59,89,175,254,244,118, 59,28,170,224,108,175,123,206,171,80, 210,166,142,120,190,114,176,151,8,12, 163,18,82,120,152,5,244,213,140,115, 176,51,56,234,191,40,41,235,178,128, 14,197,246,2,222,114,122,87,183,238, 108,90,64,166,130,94,243,70,33,165, 20,37,222,143,65,225,130,199,91,177, 139,254,110,126,172,188,211,204,107,219, 1,30,118,138,121,104,194,187,19,127, 99,107,132,78,91,93,27,228,59,10, 139,87,100,159,31,109,56,201 |
no key |