Instantly share code, notes, and snippets.

Embed
What would you like to do?
Demonstrates that an RSA signature does not uniquely identify a public key.
/*
* Demonstrates that an RSA signature does not uniquely identify a public key.
* Given a signature, s, and a message m, it's possible to construct a new RSA key
* pair such that s is a valid signature for m under the new key pair.
*
* Requires Go version >= 1.5. Go <= 1.4 doesn't work due to a bug in the bignum
* package: https://github.com/golang/go/issues/9826
*
* Written in 2015 by Andrew Ayer <agwa@andrewayer.name>
*
* To the extent possible under law, the author(s) have dedicated all
* copyright and related and neighboring rights to this software to the
* public domain worldwide. This software is distributed without any
* warranty.
*
* You should have received a copy of the CC0 Public
* Domain Dedication along with this software. If not, see
* <http://creativecommons.org/publicdomain/zero/1.0/>.
*/
package main
import (
"crypto/rsa"
"crypto"
"crypto/sha256"
"crypto/rand"
"math/big"
"fmt"
"os"
)
// Pad the given hash with PKCS#1 v1.5.
// hash and hashed are the same as the arguments to rsa.SignPKCS1v15
func padPKCS1v15 (hash crypto.Hash, hashed []byte) ([]byte) {
// Go's RSA library doesn't expose its padding functions, so just sign using
// a dummy RSA key with d=1.
var biggestInt = new(big.Int).Lsh(big.NewInt(1), 2040)
var privkey = rsa.PrivateKey{PublicKey: rsa.PublicKey{N: biggestInt, E: 1}, D: big.NewInt(1)}
var s, err = rsa.SignPKCS1v15(nil, &privkey, hash, hashed)
if err != nil {
panic("rsa.SignPKCS1v15 (from padPKCS1v15) failed: " + err.Error())
}
return s
}
// Given an RSA signature, sig, and a padded message, mesg, return an RSA key pair
// such that sig is a valid signature for mesg under the key.
func cookKey (sig []byte, mesg []byte) (rsa.PublicKey, rsa.PrivateKey) {
var sigBignum = new(big.Int).SetBytes(sig)
var mesgBignum = new(big.Int).SetBytes(mesg)
if sigBignum.Cmp(mesgBignum) <= 0 {
panic("sig is <= mesg")
}
var pubkey = rsa.PublicKey{N: new(big.Int).Sub(sigBignum, mesgBignum), E: 1}
var privkey = rsa.PrivateKey{PublicKey: pubkey, D: big.NewInt(1)}
return pubkey, privkey
}
func main() {
// 1. Generate a private key for the victim and use it to sign a message
victim_privkey, err := rsa.GenerateKey(rand.Reader, 2048)
if err != nil {
panic("rsa.GenerateKey failed: " + err.Error())
}
victim_mesg := []byte("Victim message")
victim_mesg_sum := sha256.Sum256(victim_mesg)
victim_sig, err := rsa.SignPKCS1v15(rand.Reader, victim_privkey, crypto.SHA256, victim_mesg_sum[:])
if err != nil {
panic("rsa.SignPKCS1v15 (victim message) failed: " + err.Error())
}
// 2. Cook an attacker key pair such that victim_sig is a valid signature for an attacker-controlled
// message under the attacker's key
attacker_mesg := []byte("Attacker message")
attacker_mesg_sum := sha256.Sum256(attacker_mesg)
attacker_pubkey, attacker_privkey := cookKey(victim_sig, padPKCS1v15(crypto.SHA256, attacker_mesg_sum[:]))
// 3. Demonstrate that attacker key pair is a functional key pair (can sign and verify)
example_mesg := []byte("Example message")
example_mesg_sum := sha256.Sum256(example_mesg)
example_sig, err := rsa.SignPKCS1v15(rand.Reader, &attacker_privkey, crypto.SHA256, example_mesg_sum[:])
if err != nil {
panic("rsa.SignPKCS1v15 (example message) failed: " + err.Error())
}
err = rsa.VerifyPKCS1v15(&attacker_pubkey, crypto.SHA256, example_mesg_sum[:], example_sig)
if err != nil {
panic("rsa.VerifyPKCS1v15 (example message) failed: " + err.Error())
}
// 4. Demonstrate that victim_sig is a valid signature from attacker_pubkey for attacker_mesg
err = rsa.VerifyPKCS1v15(&attacker_pubkey, crypto.SHA256, attacker_mesg_sum[:], victim_sig)
if err != nil {
panic("rsa.VerifyPKCS1v15 (attacker message) failed: " + err.Error())
}
fmt.Fprintf(os.Stdout, "Success\n")
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment