Verification of forged signature

[ryanprinster]

I have forged the signature and am verifying as I go (for sanity) that the hash of the block I am working with is equal to the public key. I have also confirmed that all of the bits in the hashed forged message that I discovered are contained in the given messages (of which we have signatures). This all works.

However, when I verify the forged message, it returns false. It seems that the public key around the 10th block is different, even when I pass the public key in directly and call the verify function myself. Any ideas why this may be?

[metalicjames]

Assuming your code passes the sign/verify tests, there is either something wrong with the section where you construct the forged signature (correlating the message bits and the revealed parts of the secret key) or where you derived the partially-revealed secret key in the first place. You can print both of these outputs to see where they differ from the original signatures provided in the problem set. That should give you a better idea of which section the bug is located in.

If you can describe a little more about how the outputs are different (with some examples of expected vs actual output), I may be able to be more helpful.

[ryanprinster]

In the forge function I iterate through the 256 bits (from the hash of the message I am verifying) to verify if they are equal to one of the 256 bits that selected the blocks in the signatures (I know that practically you would have to verify which they were with the public key but I just skipped that since you guys gave us the messages corresponding to the 4 signatures and it can be precomputed anyways).

As I iterate through these bits, I expect the hash of the block of the signature that I chose to match the block of the public key.

In the forge function, I print out the index of the bit that I am looking at (bit 9), the each time it tries a bit from one of the provided signatures ((0==1) (1==1)), the hash of the block of the corresponding signature ( hashsig: [10111000 ... ) and the block of the public key it should be equal to (pubkey: [10111000 ).

In the verify function, I do the same thing minus printing the similar bits, because that doesnt happen in the function.

This is the problem: at the index 9 bit this happens, showing that the public key is different, even when I am passing this same public key as in the forge function (i.e. I am calling verify from the forge function).

In the forge function:

bit 9 (0==1) (1==1)
hashsig: [10111000 111010 1110101 110001 10011111 10101101 10110010 10100001 10010 10001 1100001 11000010 10010000 1110 10100001 101000 11000010 11100011 11001110 111010 1010110 101111 10100001 1001001 11000110 10011001 10001001 11100 10010101 111010 10001101 11100110]
pubkey: [10111000 111010 1110101 110001 10011111 10101101 10110010 10100001 10010 10001 1100001 11000010 10010000 1110 10100001 101000 11000010 11100011 11001110 111010 1010110 101111 10100001 1001001 11000110 10011001 10001001 11100 10010101 111010 10001101 11100110]

In the verify function:

9
hashsig: [10111000 111010 1110101 110001 10011111 10101101 10110010 10100001 10010 10001 1100001 11000010 10010000 1110 10100001 101000 11000010 11100011 11001110 111010 1010110 101111 10100001 1001001 11000110 10011001 10001001 11100 10010101 111010 10001101 11100110]
pubkey: [10011011 100101 11110 10001001 101010 11000010 11101100 11000110 1011110 10000010 1011111 1010101 11100100 10011001 100010 11000001 1111001 10101011 11100100 11110000 1111100 1001 1000100 1001001 11000100 10110001 1 10001100 101111 111111 10001100 1101100]

extra stuff for reference:

Good example: works fine here.

0 
(0==1) (1==1)
hashsig: [101001 11000101 11011011 1010101 1010110 10010000 10100 1001011 10011001 111111 111100 11010011 11011 11101101 10100000 1100000 11001010 11101 11100111 1100011 10111111 11001011 110111 1011000 10101010 10111000 1100 10100111 1000011 11111110 1010 11110011]
pubkey: [101001 11000101 11011011 1010101 1010110 10010000 10100 1001011 10011001 111111 111100 11010011 11011 11101101 10100000 1100000 11001010 11101 11100111 1100011 10111111 11001011 110111 1011000 10101010 10111000 1100 10100111 1000011 11111110 1010 11110011]

0
hashsig: [101001 11000101 11011011 1010101 1010110 10010000 10100 1001011 10011001 111111 111100 11010011 11011 11101101 10100000 1100000 11001010 11101 11100111 1100011 10111111 11001011 110111 1011000 10101010 10111000 1100 10100111 1000011 11111110 1010 11110011]
pubkey: [101001 11000101 11011011 1010101 1010110 10010000 10100 1001011 10011001 111111 111100 11010011 11011 11101101 10100000 1100000 11001010 11101 11100111 1100011 10111111 11001011 110111 1011000 10101010 10111000 1100 10100111 1000011 11111110 1010 11110011]

Example of how the forge function finds a message that works:

255 (1==0) (1==0) (0==0)
hashsig: [11110 111000 10011000 10110010 11111111 100110 11100100 11110100 10101011 101011 10000100 11010000 10111101 1110001 11100110 10101101 110010 1100 1010101 10100111 11000101 11100111 11011100 1110001 11001100 11011000 101010 10100010 10101000 1001 11011 1101111]
pubkey: [11110 111000 10011000 10110010 11111111 100110 11100100 11110100 10101011 101011 10000100 11010000 10111101 1110001 11100110 10101101 110010 1100 1010101 10100111 11000101 11100111 11011100 1110001 11001100 11011000 101010 10100010 10101000 1001 11011 1101111]
true

[narula]

Hi @ryanprinster. If you haven't worked this out already, could you send your forge() function to the staff mailing list, including an example where things fail? It might be easier to debug that way.

Also just to confirm -- you are iterating until you have a message where you can actually find the bit in one of the 4 signed messages, right? For some of the bits, the signed messages have all 1s or all 0s in that spot, constraining your possible messages.