The BiBa One Time Signature is used to sign messages, and where we search for hash collisions in signing a message [article][paper]:
BiBa One Time 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].