15c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/* 25c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Copyright (c) 1996, David Mazieres <dm@uun.org> 35c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Copyright (c) 2008, Damien Miller <djm@openbsd.org> 45c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 55c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Permission to use, copy, modify, and distribute this software for any 65c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * purpose with or without fee is hereby granted, provided that the above 75c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * copyright notice and this permission notice appear in all copies. 85c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 95c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/* 195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Arc4 random number generator for OpenBSD. 205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * This code is derived from section 17.1 of Applied Cryptography, 225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * second edition, which describes a stream cipher allegedly 235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * compatible with RSA Labs "RC4" cipher (the actual description of 245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * which is a trade secret). The same algorithm is used as a stream 255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * cipher called "arcfour" in Tatu Ylonen's ssh package. 265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * RC4 is a registered trademark of RSA Laboratories. 285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#include "config.h" 31d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles)#include "wtf/CryptographicallyRandomNumber.h" 325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 33d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles)#include "wtf/StdLibExtras.h" 34d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles)#include "wtf/Threading.h" 35d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles)#include "wtf/ThreadingPrimitives.h" 365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)namespace WTF { 385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3993ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)static RandomNumberSource sourceFunction; 4093ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) 4193ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)void setRandomSource(RandomNumberSource source) 4293ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles){ 4393ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) sourceFunction = source; 4493ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)} 4593ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) 465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)namespace { 475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)class ARC4Stream { 495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)public: 505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ARC4Stream(); 515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint8_t i; 535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint8_t j; 545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint8_t s[256]; 555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)class ARC4RandomNumberGenerator { 585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) WTF_MAKE_FAST_ALLOCATED; 595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)public: 605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ARC4RandomNumberGenerator(); 615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint32_t randomNumber(); 635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void randomValues(void* buffer, size_t length); 645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)private: 665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline void addRandomData(unsigned char *data, int length); 675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void stir(); 685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void stirIfNeeded(); 695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline uint8_t getByte(); 705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline uint32_t getWord(); 715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ARC4Stream m_stream; 735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int m_count; 745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Mutex m_mutex; 755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)ARC4Stream::ARC4Stream() 785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (int n = 0; n < 256; n++) 805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) s[n] = n; 815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) i = 0; 825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) j = 0; 835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)ARC4RandomNumberGenerator::ARC4RandomNumberGenerator() 865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) : m_count(0) 875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)void ARC4RandomNumberGenerator::addRandomData(unsigned char* data, int length) 915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_stream.i--; 935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (int n = 0; n < 256; n++) { 945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_stream.i++; 955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint8_t si = m_stream.s[m_stream.i]; 965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_stream.j += si + data[n % length]; 975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_stream.s[m_stream.i] = m_stream.s[m_stream.j]; 985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_stream.s[m_stream.j] = si; 995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_stream.j = m_stream.i; 1015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 1025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)void ARC4RandomNumberGenerator::stir() 1045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 1055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) unsigned char randomness[128]; 1065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) size_t length = sizeof(randomness); 10793ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) (*sourceFunction)(randomness, length); 1085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) addRandomData(randomness, length); 1095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Discard early keystream, as per recommendations in: 1115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/Rc4_ksa.ps 1125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (int i = 0; i < 256; i++) 1135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) getByte(); 1145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_count = 1600000; 1155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 1165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)void ARC4RandomNumberGenerator::stirIfNeeded() 1185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 1195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (m_count <= 0) 1205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) stir(); 1215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 1225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)uint8_t ARC4RandomNumberGenerator::getByte() 1245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 1255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_stream.i++; 1265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint8_t si = m_stream.s[m_stream.i]; 1275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_stream.j += si; 1285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint8_t sj = m_stream.s[m_stream.j]; 1295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_stream.s[m_stream.i] = sj; 1305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_stream.s[m_stream.j] = si; 1315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return (m_stream.s[(si + sj) & 0xff]); 1325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 1335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)uint32_t ARC4RandomNumberGenerator::getWord() 1355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 1365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint32_t val; 1375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) val = getByte() << 24; 1385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) val |= getByte() << 16; 1395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) val |= getByte() << 8; 1405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) val |= getByte(); 1415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return val; 1425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 1435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)uint32_t ARC4RandomNumberGenerator::randomNumber() 1455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 1465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) MutexLocker locker(m_mutex); 1475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_count -= 4; 1495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) stirIfNeeded(); 1505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return getWord(); 1515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 1525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)void ARC4RandomNumberGenerator::randomValues(void* buffer, size_t length) 1545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 1555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) MutexLocker locker(m_mutex); 1565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) unsigned char* result = reinterpret_cast<unsigned char*>(buffer); 1585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) stirIfNeeded(); 1595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (length--) { 1605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_count--; 1615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) stirIfNeeded(); 1625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) result[length] = getByte(); 1635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 1655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)ARC4RandomNumberGenerator& sharedRandomNumberGenerator() 1675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 168d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles) AtomicallyInitializedStatic(ARC4RandomNumberGenerator*, randomNumberGenerator = new ARC4RandomNumberGenerator); 169d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles) return *randomNumberGenerator; 1705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 1715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 1735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 17493ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) 1755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)uint32_t cryptographicallyRandomNumber() 1765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 1775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return sharedRandomNumberGenerator().randomNumber(); 1785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 1795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)void cryptographicallyRandomValues(void* buffer, size_t length) 1815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 1825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) sharedRandomNumberGenerator().randomValues(buffer, length); 1835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 1845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 186