Created
July 24, 2018 22:50
-
-
Save sisou/8567592c6761bdbc845687b02725a9f9 to your computer and use it in GitHub Desktop.
Nimiq Hierarchical Deterministic Key Derivation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<!DOCTYPE html> | |
<html> | |
<head> | |
<meta charset="UTF-8"> | |
<title>Nimiq Key Derivation</title> | |
<script src="https://rawgit.com/emn178/js-sha512/master/build/sha512.min.js"></script> | |
<script src="https://cdn.nimiq.com/web-offline.js"></script> | |
<script> | |
// Load Nimiq WASM module and run test | |
Nimiq.WasmHelper.doImportBrowser().then(test); | |
/////////////////////////////////////////////////////////////////////////////// | |
///////////////////////// I M P L E M E N T A T I O N ///////////////////////// | |
/////////////////////////////////////////////////////////////////////////////// | |
function hmacSha512(key, data) { | |
if (typeof key === 'string') key = Nimiq.BufferUtils.fromHex(key); | |
if (typeof data === 'string') data = Nimiq.BufferUtils.fromHex(data); | |
if (key.length > 128) key = new Nimiq.SerialBuffer(sha512.digest(key)); | |
const iKey = new Nimiq.SerialBuffer(128); | |
const oKey = new Nimiq.SerialBuffer(128); | |
for (var i = 0; i < 128; ++i) { | |
var b = key[i] || 0; | |
iKey[i] = 0x36 ^ b; | |
oKey[i] = 0x5c ^ b; | |
} | |
const bConcatInnerAndData = new Nimiq.SerialBuffer(iKey.length + data.length); | |
bConcatInnerAndData.write(iKey); | |
bConcatInnerAndData.write(data); | |
const hashedInnerAndData = sha512.digest(bConcatInnerAndData); | |
const bConcatOuterAndHashedInnerAndData = new Nimiq.SerialBuffer(oKey.length + hashedInnerAndData.length); | |
bConcatOuterAndHashedInnerAndData.write(oKey); | |
bConcatOuterAndHashedInnerAndData.write(hashedInnerAndData); | |
const hash = sha512.digest(bConcatOuterAndHashedInnerAndData); | |
return hash; | |
} | |
function masterKey(seed) { | |
const bCurve = BufferUtils.fromAscii('ed25519 seed'); | |
const hash = hmacSha512(bCurve, seed); | |
return { | |
key: hash.slice(0, 32), | |
chainCode: hash.slice(32) | |
}; | |
} | |
function derive(extKey, index) { | |
// Only hardened derivation is allowed for ed25519 | |
if (index < 0x80000000) index += 0x80000000; | |
const data = new Nimiq.SerialBuffer(1 + extKey.key.length + 4); | |
data.writeUint8(0); | |
data.write(new Nimiq.SerialBuffer(extKey.key)); | |
data.writeUint32(index); | |
const hash = hmacSha512(extKey.chainCode, data); | |
return { | |
key: hash.slice(0, 32), | |
chainCode: hash.slice(32) | |
}; | |
} | |
function isValidPath(path) { | |
if (path.match(/^m(\/[0-9]+')*$/) === null) return false; | |
// Overflow check | |
const segments = path.split('/'); | |
for (let i = 1; i < segments.length; i++) { | |
if (parseInt(segments[i]) > 0xffffffff) return false; | |
} | |
return true; | |
} | |
function deriveForPath(path, seed) { | |
if (!isValidPath(path)) throw new Error('Invalid path'); | |
let extKey = masterKey(seed); | |
const segments = path.split('/'); | |
for (let i = 1; i < segments.length; i++) { | |
const index = parseInt(segments[i]); | |
extKey = derive(extKey, index); | |
} | |
return extKey; | |
} | |
function keyToPrivateKey(extKey) { | |
return Nimiq.PrivateKey.unserialize(new Nimiq.SerialBuffer(extKey.key)); | |
} | |
function keyToAddress(extKey) { | |
const privKey = keyToPrivateKey(extKey); | |
const pubKey = Nimiq.PublicKey.derive(privKey); | |
return pubKey.toAddress().toUserFriendlyAddress(); | |
} | |
/////////////////////////////////////////////////////////////////////////////// | |
////////////////////////////////// T E S T S ////////////////////////////////// | |
/////////////////////////////////////////////////////////////////////////////// | |
let testsSuccessfull = true; | |
function test_hmacSha512() { | |
// Test vectors from https://tools.ietf.org/html/rfc4231 | |
const vectors = [ | |
{ | |
key: '0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b', | |
data: '4869205468657265', | |
hash: '87aa7cdea5ef619d4ff0b4241a1d6cb02379f4e2ce4ec2787ad0b30545e17cdedaa833b7d6b8a702038b274eaea3f4e4be9d914eeb61f1702e696c203a126854' | |
}, | |
{ | |
key: '4a656665', | |
data: '7768617420646f2079612077616e7420666f72206e6f7468696e673f', | |
hash: '164b7a7bfcf819e2e395fbe73b56e0a387bd64222e831fd610270cd7ea2505549758bf75c05a994a6d034f65f8f0e6fdcaeab1a34d4a6b4b636e070a38bce737' | |
}, | |
{ | |
key: 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa', | |
data: 'dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd', | |
hash: 'fa73b0089d56a284efb0f0756c890be9b1b5dbdd8ee81a3655f83e33b2279d39bf3e848279a722c806b485a47e67c807b946a337bee8942674278859e13292fb' | |
}, | |
{ | |
key: '0102030405060708090a0b0c0d0e0f10111213141516171819', | |
data: 'cdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcd', | |
hash: 'b0ba465637458c6990e5a8c5f61d4af7e576d97ff94b872de76f8050361ee3dba91ca5c11aa25eb4d679275cc5788063a5f19741120c4f2de2adebeb10a298dd' | |
}, | |
{ | |
key: '0c0c0c0c0c0c0c0c0c0c0c0c0c0c0c0c0c0c0c0c', | |
data: '546573742057697468205472756e636174696f6e', | |
hash: '415fad6271580a531d4179bc891d87a6' | |
}, | |
{ | |
key: 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa', | |
data: '54657374205573696e67204c6172676572205468616e20426c6f636b2d53697a65204b6579202d2048617368204b6579204669727374', | |
hash: '80b24263c7c1a3ebb71493c1dd7be8b49b46d1f41b4aeec1121b013783f8f3526b56d037e05f2598bd0fd2215d6a1e5295e64f73f63f0aec8b915a985d786598' | |
}, | |
{ | |
key: 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa', | |
data: '5468697320697320612074657374207573696e672061206c6172676572207468616e20626c6f636b2d73697a65206b657920616e642061206c6172676572207468616e20626c6f636b2d73697a6520646174612e20546865206b6579206e6565647320746f20626520686173686564206265666f7265206265696e6720757365642062792074686520484d414320616c676f726974686d2e', | |
hash: 'e37b6a775dc87dbaa4dfa9f96e5e3ffddebd71f8867289865df5a32d20cdc944b6022cac3c4982b10d5eeb55c3e4de15134676fb6de0446065c97440fa8c6a58' | |
}, | |
]; | |
for (let i = 0; i < vectors.length; i++) { | |
const vector = vectors[i]; | |
let hash = Nimiq.BufferUtils.toHex(hmacSha512(vector.key, vector.data)); | |
if (i === 4) hash = hash.substr(0, 32); | |
if (hash !== vector.hash) testsSuccessfull = false; | |
} | |
} | |
function test_keyDerivation() { | |
// Test vectors from https://github.com/satoshilabs/slips/blob/master/slip-0010.md | |
const seeds = [ | |
'000102030405060708090a0b0c0d0e0f', | |
'fffcf9f6f3f0edeae7e4e1dedbd8d5d2cfccc9c6c3c0bdbab7b4b1aeaba8a5a29f9c999693908d8a8784817e7b7875726f6c696663605d5a5754514e4b484542' | |
]; | |
const vectors = [ | |
[ | |
{ | |
path: "m", | |
chainCode: '90046a93de5380a72b5e45010748567d5ea02bbf6522f979e05c0d8d8ca9fffb', | |
private: '2b4be7f19ee27bbf30c667b642d5f4aa69fd169872f8fc3059c08ebae2eb19e7', | |
public: '00a4b2856bfec510abab89753fac1ac0e1112364e7d250545963f135f2a33188ed' | |
}, | |
{ | |
path: "m/0'", | |
chainCode: '8b59aa11380b624e81507a27fedda59fea6d0b779a778918a2fd3590e16e9c69', | |
private: '68e0fe46dfb67e368c75379acec591dad19df3cde26e63b93a8e704f1dade7a3', | |
public: '008c8a13df77a28f3445213a0f432fde644acaa215fc72dcdf300d5efaa85d350c' | |
}, | |
{ | |
path: "m/0'/1'", | |
chainCode: 'a320425f77d1b5c2505a6b1b27382b37368ee640e3557c315416801243552f14', | |
private: 'b1d0bad404bf35da785a64ca1ac54b2617211d2777696fbffaf208f746ae84f2', | |
public: '001932a5270f335bed617d5b935c80aedb1a35bd9fc1e31acafd5372c30f5c1187' | |
}, | |
{ | |
path: "m/0'/1'/2'", | |
chainCode: '2e69929e00b5ab250f49c3fb1c12f252de4fed2c1db88387094a0f8c4c9ccd6c', | |
private: '92a5b23c0b8a99e37d07df3fb9966917f5d06e02ddbd909c7e184371463e9fc9', | |
public: '00ae98736566d30ed0e9d2f4486a64bc95740d89c7db33f52121f8ea8f76ff0fc1' | |
}, | |
{ | |
path: "m/0'/1'/2'/2'", | |
chainCode: '8f6d87f93d750e0efccda017d662a1b31a266e4a6f5993b15f5c1f07f74dd5cc', | |
private: '30d1dc7e5fc04c31219ab25a27ae00b50f6fd66622f6e9c913253d6511d1e662', | |
public: '008abae2d66361c879b900d204ad2cc4984fa2aa344dd7ddc46007329ac76c429c' | |
}, | |
{ | |
path: "m/0'/1'/2'/2'/1000000000'", | |
chainCode: '68789923a0cac2cd5a29172a475fe9e0fb14cd6adb5ad98a3fa70333e7afa230', | |
private: '8f94d394a8e8fd6b1bc2f3f49f5c47e385281d5c17e65324b0f62483e37e8793', | |
public: '003c24da049451555d51a7014a37337aa4e12d41e485abccfa46b47dfb2af54b7a' | |
} | |
], | |
[ | |
{ | |
path: "m", | |
chainCode: 'ef70a74db9c3a5af931b5fe73ed8e1a53464133654fd55e7a66f8570b8e33c3b', | |
private: '171cb88b1b3c1db25add599712e36245d75bc65a1a5c9e18d76f9f2b1eab4012', | |
public: '008fe9693f8fa62a4305a140b9764c5ee01e455963744fe18204b4fb948249308a' | |
}, | |
{ | |
path: "m/0'", | |
chainCode: '0b78a3226f915c082bf118f83618a618ab6dec793752624cbeb622acb562862d', | |
private: '1559eb2bbec5790b0c65d8693e4d0875b1747f4970ae8b650486ed7470845635', | |
public: '0086fab68dcb57aa196c77c5f264f215a112c22a912c10d123b0d03c3c28ef1037' | |
}, | |
{ | |
path: "m/0'/2147483647'", | |
chainCode: '138f0b2551bcafeca6ff2aa88ba8ed0ed8de070841f0c4ef0165df8181eaad7f', | |
private: 'ea4f5bfe8694d8bb74b7b59404632fd5968b774ed545e810de9c32a4fb4192f4', | |
public: '005ba3b9ac6e90e83effcd25ac4e58a1365a9e35a3d3ae5eb07b9e4d90bcf7506d' | |
}, | |
{ | |
path: "m/0'/2147483647'/1'", | |
chainCode: '73bd9fff1cfbde33a1b846c27085f711c0fe2d66fd32e139d3ebc28e5a4a6b90', | |
private: '3757c7577170179c7868353ada796c839135b3d30554bbb74a4b1e4a5a58505c', | |
public: '002e66aa57069c86cc18249aecf5cb5a9cebbfd6fadeab056254763874a9352b45' | |
}, | |
{ | |
path: "m/0'/2147483647'/1'/2147483646'", | |
chainCode: '0902fe8a29f9140480a00ef244bd183e8a13288e4412d8389d140aac1794825a', | |
private: '5837736c89570de861ebc173b1086da4f505d4adb387c6a1b1342d5e4ac9ec72', | |
public: '00e33c0f7d81d843c572275f287498e8d408654fdf0d1e065b84e2e6f157aab09b' | |
}, | |
{ | |
path: "m/0'/2147483647'/1'/2147483646'/2'", | |
chainCode: '5d70af781f3a37b829f0d060924d5e960bdc02e85423494afc0b1a41bbe196d4', | |
private: '551d333177df541ad876a60ea71f00447931c0a9da16f227c11ea080d7391b8d', | |
public: '0047150c75db263559a70d5778bf36abbab30fb061ad69f69ece61a72b0cfa4fc0' | |
} | |
] | |
]; | |
for (let i = 0; i < vectors.length; i++) { | |
for (let j = 0; j < vectors[i].length; j++) { | |
const vector = vectors[i][j]; | |
const extKey = deriveForPath(vector.path, seeds[i]); | |
const chainCode = Nimiq.BufferUtils.toHex(extKey.chainCode); | |
const privateKey = keyToPrivateKey(extKey); | |
const publicKey = Nimiq.PublicKey.derive(privateKey); | |
if (chainCode !== vector.chainCode | |
|| privateKey.toHex() !== vector.private | |
|| '00' + publicKey.toHex() !== vector.public | |
) testsSuccessfull = false; | |
} | |
} | |
} | |
function test() { | |
test_hmacSha512() | |
test_keyDerivation(); | |
if (testsSuccessfull) document.body.innerHTML = '<h1 style="color:green">All tests passed!</h1>'; | |
else document.body.innerHTML = '<h1 style="color:red">Tests failed!</h1>'; | |
} | |
</script> | |
</head> | |
<body></body> | |
</html> |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment