The BiBa One Time Signature is used to sign messages, and where we search for hash collisions in signing a message [article][paper][1]. 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^{256}\) 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 \(\pmod N\) function on the hash, and where \(N\) is the number of bins. If we select \(2^{10}\) there will be 1,024 bins.
BiBa One Time Signature |
Overview
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 (\textrm{Not win on second throw}) = \frac{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(\textrm{Not win on third throw}) = \frac{4}{5} \times \frac{3}{5} = \frac{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.
With BiBa (Bins and Balls), 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^{256}\) 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 \(\pmod N\) function on the hash, and where \(N\) is the number of bins. If we select \(2^{10} 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^{10}\) 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.
BiBa
One area where we can use this collision is within a one-time signature (OTS) and with the method defined as "BiBa" ("Bins and Balls").
Basically with BiBa, 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 would then publish (\(x_i, x_j\)) as the signature of the message.
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).
Code
The coding to determine a collision and generate the signature is:
import hashlib; import random bins=(2**10) private=random.randint(0,2**32) msg="the boy stood on the burning deck" bintarget=int(hashlib.sha1((msg+str(private)).encode()).hexdigest(), 16) % bins bintest=-1 count=1 print ("\nMessage: ",msg) while (bintest!=bintarget): bintest=int(hashlib.sha1((msg+str(count)).encode()).hexdigest(), 16) % bins count=count+1 print (bintest,end=' ') print ("\n\nFound at:", bintest,bintarget) print ("\nCount:", count-1) val1=int(hashlib.sha1((msg+str(count-1)).encode()).hexdigest(), 16) % bins val2=int(hashlib.sha1((msg+str(private)).encode()).hexdigest(), 16) % bins print ("Check for bins:", val1,val2) print ("Bob's private key: ",private) print ("Bob's sign value: ",count-1)
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 46 1021 691 655 782 1016 1000 489 330 595 481 144 152 437 814 101 119 660 963 669 476 379 761 631 550 59 663 665 136 549 207 901 8 87 282 517 507 971 294 79 859 636 408 90 623 302 654 663 689 253 709 105 900 960 131 820 989 629 352 639 577 897 746 251 1023 229 304 982 482 124 64 1003 17 1 497 457 155 58 560 338 771 799 378 5 50 98 522 800 338 546 403 0 932 537 421 242 44 411 603 308 695 18 4 299 277 298 253 597 150 806 290 670 541 455 813 394 573 354 68 574 324 312 13 619 428 71 608 955 435 68 756 158 758 98 202 372 2 24 259 294 103 880 620 259 748 589 438 907 750 767 21 1020 295 58 ... 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 221Found at: 221 221Count: 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.
References
[1] Perrig, A. (2001, November). The BiBa one-time signature and broadcast authentication protocol. In Proceedings of the 8th ACM Conference on Computer and Communications Security (pp. 28-37) [paper].