Dreaming BiBa

I had a dream last night. I was at a fair ground, and I was throwing balls into cans, and where I would win a prize if I could get two…

Dreaming BiBa

I am a great believer in the power of sleep, and how we can use it to solve technical problems. So, I had a dream a while ago, and I was at a fairground. As you may remember from our youth, a popular amusement is throwing balls into cans. In my dream,you win a prize if you could get two balls in the same can. My dream came from me thinking about BiBa — Bins and Balls — and which is a post-quantum crypto method for signing messages. When I woke up, and I had the answer on how BiBa relates to signing messages.

At the fairground

Let’s say you are at the fairground, and where there are five bins, and you randomly throw balls into the bins and win get two balls in the bin after three throws. Of course, the probability of the first throw will be:

P_0 = 0

on the second we now have a one-in-5 chance of getting it in the bin we hit the first time, so the chances of us not winning will be:

P_1 (Not win on second throw) = 4/5

Now, on the third throw, if we have not won, we will have two bins with balls out of 5 bins. So the bins could be:

1 1 0 0 0
1 0 1 0 0
1 0 0 1 0
1 0 0 0 1
0 1 1 0 0
0 1 0 1 0
0 1 0 0 1
0 1 0 1 0
0 1 0 0 1
You have three spaces that we could hit in each of the bins. You thus have two chances to hit a bin with a ball, and three chances to miss. The chance of you not winning is 3/5. The probability you will not win at this point is thus:

P(Not win on third throw) = 4/5 x 3/5 = 12/25 = 0.48

You now have a 52% of getting at least two balls in a bin on the third throw. Within hashing methods, this is known as a collision, and where we could group our hashes into a number of bins.

My dream

So let me explain my dream. It is all based on this classic paper [here]:

Basically the method involves us taking a hash of a value using a standard hashing method, such as with SHA-256. There will then be 2²⁵⁶ different hashing values. We aim to create a signature for a message, so Bob (the signer) selects a number of random values for his private key value and then publishes the hash of each of these (P_1, P_2, etc). He then sends these public keys to Alice. Now when Bob wants to sign a message, he will take one of his private key values, and then hashes it, and then determines the bin that it should be placed. In this case, we could use the (mod N) function on the hash, and where N is the number of bins. If we select 2¹⁰ there will be 1,024 bins. In this way there will be multiple mappings of the hash values to each of the bins:

Now when Bob takes a message, he takes the message and then adds a counter value (Ctr) on:

Message || Ctr

For each of these, he hashes and then maps to the bin. If he matches the bin for his private key value, he has found a match, otherwise, he will increment Ctr and try again. For Bob, it should not take too many tries before he finds one. When he does, he publishes the messages, and his private key value, along with the Ctr value. When Alice receives she checks that the private key value is mapped to one of this public keys, and then that the Ctr value maps to the same bin. If it does, the signature was produced by Bob.

Here is some code and where I have used 2¹⁰ bins, and the SHA-256 hash:

In this case, Bob selects one of his private keys (“55”), and must now find a value which will fit the same bin. We see that 407 values are tried, and finally, we get a match on Ctr=406:

Message:  the boy stood on the burning deck
497 51 858 450 250 675 385 597 317 407 491 36 992 561 553 996 478
 519 635 634 504 236 917 170 809 837 517 346 980 698 304 747 820 
445 414 18 367 870 60 409 960 242 584 932 979 485 367 840 687 91 
408 217 438 679 516 306 546 593 671 170 223 230 147 770 436 1016 
509 386 490 653 886 811 906 169 704 773 159 163 561 833 344 814 1
05 249 533 971 495 722 572 927 866 883 304 250 346 547 815 364 37
2 18 233 475 213 531 929 66 281 175 694 345 727 169 589 844 377 7
36 78 629 20 906 841 304 549 930 894 659 828 67 647 603 669 253 1
89 120 605 728 389 652 879 955 678 864 781 942 1007 480 309 224 2
7 212 680 197 882 855 904 484 288 1017 705 107 769 644 516 731 73
8 706 957 27 601 181 250 319 789 53 892 698 914 32 418 434 405 63
5 804 265 988 928 366 620 627 237 321 377 758 569 423 514 277 141
 955 165 418 90 309 971 103 111 1002 443 233 333 230 553 169 582 
551 645 351 972 598 919 579 670 523 230 800 739 25 486 753 114 18
1 572 395 863 519 231 246 236 226 788 88 84 737 926 840 865 853 1
... 5 590 194 96 433 160 196 61 667 234 846 299 274 892 313 138 838 127 641 755 782 681 985 267 432 50 626 94 395 695 559 688 75 790 1010 757 370 426 671 91 595 703 753 756 77 338 56 746 939 527 390 926 898 993 659 953 764 648 846 87 511 858 893 778 431 549 72 601 302 279 182 114 21 892 881 154 834 765 624 565 778 814 776 476 478 62 595 508 706 357 270 155 638 1021 233 898 797 612 863 172 914 854 7 999 887 914 591 655 671 12 449 414 758 26 620 779 530 72 909 11 503 566 128 938 415 817 472 570 847 980 4 673 561 497 995 715 483 217 458 246 654 988 764 766 77 152 222 115 603 623 463 215 242 684 913 132 17 272 88 818 824 587 347 342 493 466 313 647 283 945 703 837 772 165 48 334 532 707 40 58 108 384 546 218 324 442 394 757 115 508 413 85 450 221

Found at: 221 221

Count: 1154
Check for bins: 221 221
Bob's private key:  1477773384
Bob's sign value:  1154

Bob thus provides the message and the values of “1477773384” and “1154”. Alice checks the hash of Bob’s private key is one of his public keys, and then checks the bins. If they match, everything is fine with the signature:

https://asecuritysite.com/hashsig/go_biba

Details

Overall BiBa is a one-time signature (OTS) method and where Bob creates a number of random values for his private key:

Priv = x_1, x_2, … x_n

Next, he creates his public key from the hashed versions of his private key:

Pub = SHA1(x_1), SHA1(x_2) … SHA1(x_n)

To create the signature for a message (M), he finds two values which will create a collision (as we have seen it should be fairly easy to find a collision within a reasonable amount of guesses):

H(M || x_i) == H(M || x_j)

He then publishes (x_i, x_j) as the signature of the message, of which of the values relates to his private key.

It would then be too difficult for Eve to find the values of x_i and x_j to create a collision, as Bob does not reveal them (they are only defined with their hash signature). We can see that the public key is quite large, but we can reduce this by storing the private keys within a Merkle tree, and where Bob shows the Merkle tree path to his private key. In this way, Bob just has to release the Merkle root of his private keys, as his public key.

Conclusions

I am a great believer in the power of sleep in solving problems, and my dream helped me solve this one.