Gareth Nelson


January 23, 2012, 01:42:40 PM 

As the topic says...
Here is my scheme: I want to encode several 32byte strings (wow, I wonder what they could be) using another 32byte string as the key.
If it was only one string I wanted to encode, i'd XOR it  problem is that if I reuse it my key can be leaked: K key C ciphertext P plaintext
K = 10 C1 = P1^K C2 = P2^K C1^P1 = K C2^P2 = K
So.........
I alternate K,after every message, I transform K into sha256(K), so that the same value of K is never used for >1 encryption.
Here's the challenge  you have all values of C but not K, break the scheme so that you can find K or any value of P and you win 5BTC. Break the scheme so that having the value of a single P gives you K or other P values and you win 5BTC.
Get cracking.








Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.




jetmine
Jr. Member
Offline
Activity: 53
Merit: 0


January 23, 2012, 02:00:55 PM 

There are (at least) two weaknesses:
1) Initially you use K, later you use SHA256 outputs. If an attacker can "somehow" undo one encryption, he learns a different thing from undoing the C1/P1 encryption versus Cn/Pn (n>1). Why not make the transform before using K rather than afterwards, so that all K's leak the same level of information?
2) You permutate the same K as used in the encryption. If an attacker can "somehow" undo one encryption, he automatically has enough information to undo all subsequent encryptions. This is especially problematic when the plaintext can be guessed. Imagine you encode a sequence of 0bits at some point. The attacker can guess that you do this, and just try Kn = Cn ^ 0 for all n, and permutate K(n+1) = SHA256(Kn) and look if P(n+1) = C(n+1) ^ K(n+1) (for all remaining n) makes sense. If not, then he tries a different Kn, until all are exhausted, and then he can still guess a different P (for example all 1bits).
To improve, you could permutate K, but instead of using it directly you could use K'n = SHA256(Kn). Then guessing Pn would not reveal Kn, and without Kn the attacker would not be able to decrypt the data n+1..max.
Keep your BTC.




Gareth Nelson


January 23, 2012, 02:14:16 PM 

There are (at least) two weaknesses:
1) Initially you use K, later you use SHA256 outputs. If an attacker can "somehow" undo one encryption, he learns a different thing from undoing the C1/P1 encryption versus Cn/Pn (n>1). Why not make the transform before using K rather than afterwards, so that all K's leak the same level of information?
To be clear, I use K first, and then use SHA256(K) and then SHA256(SHA256(K)) and then SHA256(SHA256(SHA256(K))), let's model this as f(K) where f is either a big pile of nested SHA256 or the identity function I. We'll call nested SHA256, H: H(K) = SHA256(SHA256(....(K)) I(K) = K You know C0, encrypted with f=I, reversing f in this case is trivial as f is a noop, how does this lead to getting the value of K or the value of P0? If you can't do it with f=I, how do you do it with f=H where the complexity is far higher? 2) You permutate the same K as used in the encryption. If an attacker can "somehow" undo one encryption, he automatically has enough information to undo all subsequent encryptions. This is especially problematic when the plaintext can be guessed. Imagine you encode a sequence of 0bits at some point. The attacker can guess that you do this, and just try Kn = Cn ^ 0 for all n, and permutate K(n+1) = SHA256(Kn) and look if P(n+1) = C(n+1) ^ K(n+1) (for all remaining n) makes sense. If not, then he tries a different Kn, until all are exhausted, and then he can still guess a different P (for example all 1bits).
To improve, you could permutate K, but instead of using it directly you could use K'n = SHA256(Kn). Then guessing Pn would not reveal Kn, and without Kn the attacker would not be able to decrypt the data n+1..max.
Keep your BTC.
Now this is a true weakness, where the attacker knows Kn, he can derive future values of K. What about if K is derived like this: K[n] = SHA256(SHA256(k[n1])+P[n]) In theory this would prevent the attacker deriving future values of K. I hereby update the challenge




kjj
Legendary
Offline
Activity: 1302
Merit: 1001


January 23, 2012, 02:17:16 PM 

As the topic says...
Here is my scheme: I want to encode several 32byte strings (wow, I wonder what they could be) using another 32byte string as the key.
If it was only one string I wanted to encode, i'd XOR it  problem is that if I reuse it my key can be leaked: K key C ciphertext P plaintext
K = 10 C1 = P1^K C2 = P2^K C1^P1 = K C2^P2 = K
So.........
I alternate K,after every message, I transform K into sha256(K), so that the same value of K is never used for >1 encryption.
Here's the challenge  you have all values of C but not K, break the scheme so that you can find K or any value of P and you win 5BTC. Break the scheme so that having the value of a single P gives you K or other P values and you win 5BTC.
Get cracking.
Basically, if anyone ever finds Pn, like if you ever use it, they now have Kn, and thus they can find all Ko and Po where o>n. Jetmine's suggestion of setting K1=SHA(K) doesn't help. K is not special, but Kn becomes special if Pn ever becomes known. Assuming that you intend P1 to be a private key, this scheme should be reasonably safe, since private keys aren't normally leaked to the network. But I don't see any advantage of using this scheme over a conventional block cipher that you would use to encrypt a random file. Also, I'm not a cryptographer. You are strongly encourages to read Schneier's books and stick to things that he says are safe to do. There may be other weaknesses in this scheme that aren't apparent to laymen, but may be known to professionals.

17Np17BSrpnHCZ2pgtiMNnhjnsWJ2TMqq8 I routinely ignore posters with paid advertising in their sigs. You should too.



kronosvl


January 23, 2012, 02:20:41 PM 

Now this is a true weakness, where the attacker knows Kn, he can derive future values of K.
What about if K is derived like this: K[n] = SHA256(SHA256(k[n1])+P[n])
In theory this would prevent the attacker deriving future values of K.
I hereby update the challenge
I'm no expert but how do you plain to recover p[n] if you have k[n1] and c[n]? (because k[n] is f(k[n1], p[n])) you would have p[n]=c[n] op f(k[n1], p[n]))




BTCurious


January 23, 2012, 02:25:06 PM 

What about if K is derived like this: K[n] = SHA256(SHA256(k[n1])+P[n]) Then you won't be able to decode it either, assuming you don't store K[n] and P[n] (which is best practice). You could just do: j[0] = 32 random bytes K[0] = SHA256(j[0]) j[1] = j[0]++ K[1] = SHA256(j[1]) j[2] = j[1]++ K[2] = SHA256(j[2]) etc. Knowing any K won't help you find the next K. You yourself only have to store or remember 32 bytes: j[0], the rest can be derived from that.




Gareth Nelson


January 23, 2012, 02:27:06 PM 

kronosvl  at time of encryption I know p[n] already, but I get what you mean  it wouldn't be possible to recover it afterwards. That's what you get for thinking out loud on a public forum Got to think about this further, but the core reason i'm not using standard crypto is because of the very short data lengths (32 bytes for key and plaintext). Let's try this: K[n] = (SHA256(K[n1])+SHA256(K[n2])) So to build the value of K you need at least 2 previous values of K.




Gareth Nelson


January 23, 2012, 02:28:32 PM 

What about if K is derived like this: K[n] = SHA256(SHA256(k[n1])+P[n]) Then you won't be able to decode it either, assuming you don't store K[n] and P[n] (which is best practice). You could just do: j[0] = 32 random bytes K[0] = SHA256(j[0]) j[1] = j[0]++ K[1] = SHA256(j[1]) j[2] = j[1]++ K[2] = SHA256(j[2]) etc. Knowing any K won't help you find the next K. You yourself only have to store or remember 32 bytes: j[0], the rest can be derived from that. Post a BTC address




BTCurious


January 23, 2012, 02:37:38 PM 

What about if K is derived like this: K[n] = SHA256(SHA256(k[n1])+P[n]) Then you won't be able to decode it either, assuming you don't store K[n] and P[n] (which is best practice). You could just do: j[0] = 32 random bytes K[0] = SHA256(j[0]) j[1] = j[0]++ K[1] = SHA256(j[1]) j[2] = j[1]++ K[2] = SHA256(j[2]) etc. Knowing any K won't help you find the next K. You yourself only have to store or remember 32 bytes: j[0], the rest can be derived from that. Post a BTC address 1NaNoBitU2q8czqE2y5rEQPj4qcW6K3mFp At first I thought this was what jetmine was suggesting actually, but the difference in his algorithm is that j[1] = SHA256(j[0]). This isn't secure since j[1] == K[0], so that wouldn't keep your 'j's hidden.





Yankee (BitInstant)
Legendary
Offline
Activity: 1078
Merit: 1000
Charlie 'Van Bitcoin' Shrem


January 23, 2012, 05:42:16 PM 

This is all so beyond me.....

Bitcoin pioneer. An apostle of Satoshi Nakamoto. A crusader for a new, better, techdriven society. A dreamer. More about me: http://CharlieShrem.com



jetmine
Jr. Member
Offline
Activity: 53
Merit: 0


January 23, 2012, 05:58:19 PM 

To be clear, I use K first, and then use SHA256(K) and then
In case I wasn't clear enough: The difference is in that when I have to guess SHA256(K) I have to guess 256 pseudorandom bits. But when I only have to guess K, then maybe a dictionary is enough (or a short bruteforce run). Also, if I can guess P1 and thus get K = C1 ^ P1, I learn something about you and about how you choose your secrets. However, if all I get from it is SHA256(K), it is a lot less useful. These are clearly weaknesses, given that a tiny modification avoids them completely. What about if K is derived like this: K[n] = SHA256(SHA256(k[n1])+P[n])
... then you can't decrypt anymore. I hereby update the challenge
The more variants you come up with per hour, the less attention (and relevant attempts of analysis) they will grab. Why not think about it for a week, attempt to crack it yourself, and when it stands, then post? At first I thought this was what jetmine was suggesting actually, but the difference in his algorithm is that j[1] = SHA256(j[0]).
The difference is that you call "K" what I call "K'", and call "j" what I call "K", and you calculate j(n+1) = j(n)+1 while I stay nearer to the GP by calculating j(n+1) = SHA256(j(n)). Using a counter is better for random access (think seek), and multithreaded implementation. However the security properties are doubtful, because you mix the counter and the key material. The longer the counter range (=max message stream size), the lower the maximum key entropy. It's advisable to calculate SHA256(counter  key) instead of SHA256(counter). Counter is then just an IV or NONCE, and you can set it to 0 at the start of the stream instead of keeping it secret. You can also apply the "classic" knowlegde of cryptography. I.e. don't use any NONCE/KEY pair twice, may reveal NONCE but not KEY, etc. There are many possible algorithms, each with different properties. It's a matter of what you expect from it, and the GP isn't particularily clear at this.




