Demonstrates that an RSA signature does not uniquely identify a public key.

cook_rsa_key.go

/*
 * 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")
}