Bitcoin Forum
March 28, 2024, 09:11:52 PM *
News: Latest Bitcoin Core release: 26.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: [OBSOLETE] Crack this for 5BTC  (Read 1669 times)
Gareth Nelson (OP)
Hero Member
*****
Offline Offline

Activity: 721
Merit: 503


View Profile
January 23, 2012, 01:42:40 PM
Last edit: January 23, 2012, 02:43:20 PM by garethnelsonuk
 #1

As the topic says...

Here is my scheme: I want to encode several 32-byte strings (wow, I wonder what they could be) using another 32-byte 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.
1711660312
Hero Member
*
Offline Offline

Posts: 1711660312

View Profile Personal Message (Offline)

Ignore
1711660312
Reply with quote  #2

1711660312
Report to moderator
1711660312
Hero Member
*
Offline Offline

Posts: 1711660312

View Profile Personal Message (Offline)

Ignore
1711660312
Reply with quote  #2

1711660312
Report to moderator
1711660312
Hero Member
*
Offline Offline

Posts: 1711660312

View Profile Personal Message (Offline)

Ignore
1711660312
Reply with quote  #2

1711660312
Report to moderator
Activity + Trust + Earned Merit == The Most Recognized Users on Bitcointalk
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction.
jetmine
Newbie
*
Offline Offline

Activity: 53
Merit: 0


View Profile
January 23, 2012, 02:00:55 PM
 #2

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 0-bits 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 1-bits).

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 (OP)
Hero Member
*****
Offline Offline

Activity: 721
Merit: 503


View Profile
January 23, 2012, 02:14:16 PM
 #3

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 no-op, 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?

Quote
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 0-bits 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 1-bits).

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[n-1])+P[n])

In theory this would prevent the attacker deriving future values of K.

I hereby update the challenge
kjj
Legendary
*
Offline Offline

Activity: 1302
Merit: 1024



View Profile
January 23, 2012, 02:17:16 PM
 #4

As the topic says...

Here is my scheme: I want to encode several 32-byte strings (wow, I wonder what they could be) using another 32-byte 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
Full Member
***
Offline Offline

Activity: 134
Merit: 100


View Profile
January 23, 2012, 02:20:41 PM
 #5

Quote

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[n-1])+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[n-1] and c[n]? (because k[n] is f(k[n-1], p[n]))
you would have p[n]=c[n] op f(k[n-1], p[n]))

Donations are accepted @: 19Uk8zVhdgfrRo5Z6wH9yghWxZUtdiNtX9
OTC: http://bitcoin-otc.com/viewgpg.php?nick=kronosvl
BTCurious
Hero Member
*****
Offline Offline

Activity: 714
Merit: 503


^SEM img of Si wafer edge, scanned 2012-3-12.


View Profile
January 23, 2012, 02:25:06 PM
 #6

What about if K is derived like this:
K[n] = SHA256(SHA256(k[n-1])+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 (OP)
Hero Member
*****
Offline Offline

Activity: 721
Merit: 503


View Profile
January 23, 2012, 02:27:06 PM
 #7

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 Wink

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[n-1])+SHA256(K[n-2]))

So to build the value of K you need at least 2 previous values of K.
Gareth Nelson (OP)
Hero Member
*****
Offline Offline

Activity: 721
Merit: 503


View Profile
January 23, 2012, 02:28:32 PM
 #8

What about if K is derived like this:
K[n] = SHA256(SHA256(k[n-1])+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 Smiley
BTCurious
Hero Member
*****
Offline Offline

Activity: 714
Merit: 503


^SEM img of Si wafer edge, scanned 2012-3-12.


View Profile
January 23, 2012, 02:37:38 PM
 #9

What about if K is derived like this:
K[n] = SHA256(SHA256(k[n-1])+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 Smiley
1NaNoBitU2q8czqE2y5rEQPj4qcW6K3mFp Smiley

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.

Gareth Nelson (OP)
Hero Member
*****
Offline Offline

Activity: 721
Merit: 503


View Profile
January 23, 2012, 02:42:24 PM
 #10

Sent!
Yankee (BitInstant)
Legendary
*
Offline Offline

Activity: 1078
Merit: 1000


Charlie 'Van Bitcoin' Shrem


View Profile WWW
January 23, 2012, 05:42:16 PM
 #11

This is all so beyond me.....

Bitcoin pioneer. An apostle of Satoshi Nakamoto. A crusader for a new, better, tech-driven society. A dreamer.

More about me: http://CharlieShrem.com
jetmine
Newbie
*
Offline Offline

Activity: 53
Merit: 0


View Profile
January 23, 2012, 05:58:19 PM
 #12

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[n-1])+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.
Pages: [1]
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!