Index: src/Makefile ================================================================== --- src/Makefile +++ src/Makefile @@ -1,6 +1,6 @@ all: objfw-compile -Wall --lib 0.0 -o objxmpp *.m \ - `pkg-config --cflags --libs libidn libbsd` + `pkg-config --cflags --libs libidn` clean: rm -f *.o *.so *.dylib *.dll Index: src/XMPPPLAINAuth.m ================================================================== --- src/XMPPPLAINAuth.m +++ src/XMPPPLAINAuth.m @@ -26,50 +26,55 @@ @implementation XMPPPLAINAuth + PLAINAuthWithAuthcid: (OFString*)authcid password: (OFString*)password { return [[[self alloc] initWithAuthcid: authcid - password: password] autorelease]; + password: password] autorelease]; } + PLAINAuthWithAuthzid: (OFString*)authzid authcid: (OFString*)authcid password: (OFString*)password { return [[[self alloc] initWithAuthzid: authzid - authcid: authcid - password: password] autorelease]; + authcid: authcid + password: password] autorelease]; } - (OFDataArray*)clientFirstMessage { OFDataArray *message = [OFDataArray dataArrayWithItemSize: 1]; + /* authzid */ if (authzid) [message addItem: authzid]; + /* separator */ [message addItem: ""]; + /* authcid */ [message addNItems: [authcid cStringLength] fromCArray: [authcid cString]]; + /* separator */ [message addItem: ""]; + /* passwd */ [message addNItems: [password cStringLength] fromCArray: [password cString]]; return message; } - (OFDataArray*)calculateResponseWithChallenge: (OFDataArray*)challenge { - @throw [XMPPAuthFailedException - newWithClass: isa - connection: nil - reason: @"Received a challenge during PLAIN auth"]; + @throw [XMPPAuthFailedException newWithClass: isa + connection: nil + reason: @"Received a challenge " + @"during PLAIN auth"]; } - (void)parseServerFinalMessage: (OFDataArray*)message { return; } @end Index: src/XMPPSCRAMAuth.h ================================================================== --- src/XMPPSCRAMAuth.h +++ src/XMPPSCRAMAuth.h @@ -42,12 +42,12 @@ * \param password The password to authenticate with * \param hash The class to use for calulating hashes * \return A new autoreleased XMPPSCRAMAuth */ + SCRAMAuthWithAuthcid: (OFString*)authcid - password: (OFString*)password - hash: (Class)hash; + password: (OFString*)password + hash: (Class)hash; /** * Creates a new autoreleased XMPPSCRAMAuth with an authzid, * authcid and password. * @@ -56,13 +56,13 @@ * \param password The password to authenticate with * \param hash The class to use for calulating hashes * \return A new autoreleased XMPPSCRAMAuth */ + SCRAMAuthWithAuthzid: (OFString*)authzid - authcid: (OFString*)authcid - password: (OFString*)password - hash: (Class)hash; + authcid: (OFString*)authcid + password: (OFString*)password + hash: (Class)hash; /** * Initializes an already allocated XMPPSCRAMAuth with an authcid and password. * * \param authcid The authcid to authenticate with @@ -70,11 +70,11 @@ * \param hash The class to use for calulating hashes * \return A initialized XMPPSCRAMAuth */ - initWithAuthcid: (OFString*)authcid password: (OFString*)password - hash: (Class)hash; + hash: (Class)hash; /** * Initializes an already allocated XMPPSCRAMAuth with a authzid, * authcid and password. * Index: src/XMPPSCRAMAuth.m ================================================================== --- src/XMPPSCRAMAuth.m +++ src/XMPPSCRAMAuth.m @@ -1,7 +1,8 @@ /* * Copyright (c) 2011, Florian Zeitz + * Copyright (c) 2011, Jonathan Schleifer * * https://webkeks.org/hg/objxmpp/ * * Permission to use, copy, modify, and/or distribute this software for any * purpose with or without fee is hereby granted, provided that the above @@ -19,23 +20,22 @@ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE * POSSIBILITY OF SUCH DAMAGE. */ #include -#include -// FIXME: Remove this once libbsd includes arc4random_uniform() in it's headers -#define fake_arc4random_uniform(upper) \ - ((uint32_t) (arc4random() / (double) UINT32_MAX * upper)) #import "XMPPSCRAMAuth.h" #import "XMPPExceptions.h" #define HMAC_IPAD 0x36 #define HMAC_OPAD 0x5c + +#ifndef HAVE_ARC4RANDOM_UNIFORM +extern uint32_t arc4random_uniform(uint32_t); +#endif @implementation XMPPSCRAMAuth - + SCRAMAuthWithAuthcid: (OFString*)authcid password: (OFString*)password hash: (Class)hash; { return [[[self alloc] initWithAuthcid: authcid @@ -91,18 +91,16 @@ - (void)setAuthzid: (OFString*)authzid_ { OFString *old = authzid; if (authzid_) { - OFMutableString *new = [[OFMutableString alloc] - initWithString: authzid_]; + OFMutableString *new = [[authzid_ mutableCopy] autorelease]; [new replaceOccurrencesOfString: @"=" withString: @"=3D"]; [new replaceOccurrencesOfString: @"," withString: @"=2C"]; - authzid = [new copy]; - [new release]; + authzid = [new retain]; } else authzid = nil; [old release]; } @@ -110,58 +108,55 @@ - (void)setAuthcid: (OFString*)authcid_ { OFString *old = authcid; if (authcid_) { - OFMutableString *new = [[OFMutableString alloc] - initWithString: authcid_]; + OFMutableString *new = [[authcid_ mutableCopy] autorelease]; [new replaceOccurrencesOfString: @"=" withString: @"=3D"]; [new replaceOccurrencesOfString: @"," withString: @"=2C"]; - authcid = [new copy]; - [new release]; + authcid = [new retain]; } else authcid = nil; [old release]; } -- (OFString *)_genNonce +- (OFString*)_genNonce { OFMutableString *nonce = [OFMutableString string]; uint32_t res, i; + for (i = 0; i < 64; i++) { - while((res = fake_arc4random_uniform(0x5e) + 0x21) == 0x2C); + while ((res = arc4random_uniform('~' - '!' + 1) + '!') == ','); [nonce appendFormat: @"%c", res]; } return nonce; } -- (uint8_t *)_hmacWithKey: (OFDataArray*)key - data: (OFDataArray*)data -{ - size_t i, kSize, blockSize = [hashType blockSize]; - uint8_t *kCArray = NULL, *kI = NULL, *kO = NULL; - OFAutoreleasePool *pool = nil; - OFDataArray *k = nil; - OFHash *hash = nil; - - @try { - pool = [[OFAutoreleasePool alloc] init]; - k = [OFDataArray dataArrayWithItemSize: 1]; - if (key.itemSize * key.count > blockSize) { - hash = [[[hashType alloc] init] autorelease]; - [hash updateWithBuffer: [key cArray] - ofSize: key.itemSize * key.count]; - [k addNItems: [hashType digestSize] - fromCArray: [hash digest]]; - } else - [k addNItems: key.itemSize * key.count - fromCArray: [key cArray]]; - +- (uint8_t*)_HMACWithKey: (OFDataArray*)key + data: (OFDataArray*)data +{ + OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init]; + OFDataArray *k = [OFDataArray dataArrayWithItemSize: 1]; + size_t i, kSize, blockSize = [hashType blockSize]; + uint8_t *kCArray, *kI = NULL, *kO = NULL; + OFHash *hash; + + if (key.itemSize * key.count > blockSize) { + hash = [[[hashType alloc] init] autorelease]; + [hash updateWithBuffer: [key cArray] + ofSize: key.itemSize * key.count]; + [k addNItems: [hashType digestSize] + fromCArray: [hash digest]]; + } else + [k addNItems: key.itemSize * key.count + fromCArray: [key cArray]]; + + @try { kI = [self allocMemoryWithSize: blockSize * sizeof(uint8_t)]; memset(kI, HMAC_IPAD, blockSize * sizeof(uint8_t)); kO = [self allocMemoryWithSize: blockSize * sizeof(uint8_t)]; memset(kO, HMAC_OPAD, blockSize * sizeof(uint8_t)); @@ -175,103 +170,108 @@ k = [OFDataArray dataArrayWithItemSize: 1]; [k addNItems: blockSize fromCArray: kI]; [k addNItems: data.itemSize * data.count - fromCArray: [data cArray]]; + fromCArray: [data cArray]]; hash = [[[hashType alloc] init] autorelease]; [hash updateWithBuffer: [k cArray] ofSize: k.count]; k = [OFDataArray dataArrayWithItemSize: 1]; [k addNItems: blockSize fromCArray: kO]; [k addNItems: [hashType digestSize] fromCArray: [hash digest]]; - - hash = [[[hashType alloc] init] autorelease]; - [hash updateWithBuffer: [k cArray] - ofSize: k.count]; - - [hash retain]; - [pool release]; - pool = nil; - [hash autorelease]; - - return [hash digest]; } @finally { - [pool release]; [self freeMemory: kI]; [self freeMemory: kO]; } + + hash = [[[hashType alloc] init] autorelease]; + [hash updateWithBuffer: [k cArray] + ofSize: k.count]; + + [hash retain]; + [pool release]; + + return [hash digest]; } -- (OFDataArray *)_hiWithData: (OFDataArray *)str - salt: (OFDataArray *)salt_ - iterationCount: (unsigned int)i +- (OFDataArray*)_hiWithData: (OFDataArray *)str + salt: (OFDataArray *)salt_ + iterationCount: (unsigned int)i { + OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init]; + size_t digestSize = [hashType digestSize]; uint8_t *result = NULL, *u, *uOld; unsigned int j, k; - size_t digestSize; - OFAutoreleasePool *pool = nil; OFDataArray *salty, *tmp, *ret; + result = [self allocMemoryWithSize: digestSize]; + @try { - pool = [[OFAutoreleasePool alloc] init]; - digestSize = [hashType digestSize]; - result = [self - allocMemoryWithSize: digestSize * sizeof(uint8_t)]; - memset(result, 0, digestSize * sizeof(uint8_t)); - salty = [salt_ copy]; + memset(result, 0, digestSize); + + salty = [[salt_ copy] autorelease]; [salty addNItems: 4 fromCArray: "\0\0\0\1"]; - uOld = [self _hmacWithKey: str + uOld = [self _HMACWithKey: str data: salty]; - [salty release]; + for (j = 0; j < digestSize; j++) result[j] ^= uOld[j]; - for (j = 0; j < i-1; j++) { + for (j = 0; j < i - 1; j++) { tmp = [OFDataArray dataArrayWithItemSize: 1]; [tmp addNItems: digestSize fromCArray: uOld]; - u = [self _hmacWithKey: str + + u = [self _HMACWithKey: str data: tmp]; + for (k = 0; k < digestSize; k++) result[k] ^= u[k]; + uOld = u; + + [pool releaseObjects]; } ret = [OFDataArray dataArrayWithItemSize: 1]; [ret addNItems: digestSize fromCArray: result]; - - [ret retain]; - [pool release]; - pool = nil; - - return [ret autorelease]; } @finally { - [pool release]; [self freeMemory: result]; } + + [ret retain]; + [pool release]; + + return [ret autorelease]; } - (OFDataArray*)clientFirstMessage { OFDataArray *ret = [OFDataArray dataArrayWithItemSize: 1]; + [GS2Header release]; + GS2Header = nil; + if (authzid) GS2Header = [[OFString alloc] initWithFormat: @"n,a=%@,", authzid]; else - GS2Header = [[OFString alloc] initWithFormat: @"n,,"]; + GS2Header = @"n,,"; [cNonce release]; + cNonce = nil; cNonce = [[self _genNonce] retain]; + [clientFirstMessageBare release]; + clientFirstMessageBare = nil; clientFirstMessageBare = [[OFString alloc] initWithFormat: @"n=%@,r=%@", authcid, cNonce]; [ret addNItems: [GS2Header cStringLength] fromCArray: [GS2Header cString]]; @@ -290,185 +290,173 @@ OFHash *hash; OFDataArray *ret, *authMessage, *tmpArray, *salt, *saltedPassword; OFString *tmpString, *sNonce; OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init]; - @try { - hash = [[[hashType alloc] init] autorelease]; - ret = [OFDataArray dataArrayWithItemSize: 1]; - authMessage = [OFDataArray dataArrayWithItemSize: 1]; - - OFString *chal = [OFString - stringWithCString: [challenge cArray] - length: - [challenge count] * [challenge itemSize]]; - - for (OFString *comp - in [chal componentsSeparatedByString: @","]) { - OFString *entry = [comp - substringFromIndex: 2 - toIndex: [comp length]]; - if ([comp hasPrefix: @"r="]) { - if (![entry hasPrefix: cNonce]) - @throw [XMPPAuthFailedException - newWithClass: isa - connection: nil - reason: - @"Received wrong nonce"]; - sNonce = entry; - } else if ([comp hasPrefix: @"s="]) - salt = [OFDataArray - dataArrayWithBase64EncodedString: entry]; - else if ([comp hasPrefix: @"i="]) - iterCount = [entry decimalValue]; - } - - // Add c= - // XXX: No channel binding for now - tmpArray = [OFDataArray dataArrayWithItemSize: 1]; - [tmpArray addNItems: [GS2Header cStringLength] - fromCArray: [GS2Header cString]]; - tmpString = [tmpArray stringByBase64Encoding]; - [ret addNItems: 2 - fromCArray: "c="]; - [ret addNItems: [tmpString cStringLength] - fromCArray: [tmpString cString]]; - - // Add r= - [ret addItem: ","]; - [ret addNItems: 2 - fromCArray: "r="]; - [ret addNItems: [sNonce cStringLength] - fromCArray: [sNonce cString]]; - - tmpArray = [OFDataArray dataArrayWithItemSize: 1]; - [tmpArray addNItems: [password cStringLength] - fromCArray: [password cString]]; - - /* - * IETF RFC 5802: - * SaltedPassword := Hi(Normalize(password), salt, i) - */ - saltedPassword = [self _hiWithData: tmpArray - salt: salt - iterationCount: iterCount]; - - /* - * IETF RFC 5802: - * AuthMessage := client-first-message-bare + "," + - * server-first-message + "," + - * client-final-message-without-proof - */ - [authMessage addNItems: [clientFirstMessageBare cStringLength] - fromCArray: [clientFirstMessageBare cString]]; - [authMessage addItem: ","]; - [authMessage addNItems: [challenge count] * [challenge itemSize] - fromCArray: [challenge cArray]]; - [authMessage addItem: ","]; - [authMessage addNItems: [ret count] - fromCArray: [ret cArray]]; - - /* - * IETF RFC 5802: - * ClientKey := HMAC(SaltedPassword, "Client Key") - */ - tmpArray = [OFDataArray dataArrayWithItemSize: 1]; - [tmpArray addNItems: 10 - fromCArray: "Client Key"]; - clientKey = [self _hmacWithKey: saltedPassword - data: tmpArray]; - - /* - * IETF RFC 5802: - * StoredKey := H(ClientKey) - */ - [hash updateWithBuffer: (void*) clientKey - ofSize: [hashType digestSize]]; - tmpArray = [OFDataArray dataArrayWithItemSize: 1]; - [tmpArray addNItems: [hashType digestSize] - fromCArray: [hash digest]]; - - /* - * IETF RFC 5802: - * ClientSignature := HMAC(StoredKey, AuthMessage) - */ - clientSignature = [self _hmacWithKey: tmpArray - data: authMessage]; - - /* - * IETF RFC 5802: - * ServerKey := HMAC(SaltedPassword, "Server Key") - */ - tmpArray = [OFDataArray dataArrayWithItemSize: 1]; - [tmpArray addNItems: 10 - fromCArray: "Server Key"]; - serverKey = [self _hmacWithKey: saltedPassword - data: tmpArray]; - - /* - * IETF RFC 5802: - * ServerSignature := HMAC(ServerKey, AuthMessage) - */ - tmpArray = [OFDataArray dataArrayWithItemSize: 1]; - [tmpArray addNItems: [hashType digestSize] - fromCArray: serverKey]; - serverSignature = [[OFDataArray alloc] initWithItemSize: 1]; - [serverSignature addNItems: [hashType digestSize] - fromCArray: [self _hmacWithKey: tmpArray - data: authMessage]]; - - /* - * IETF RFC 5802: - * ClientProof := ClientKey XOR ClientSignature - */ - tmpArray = [OFDataArray dataArrayWithItemSize: 1]; - for (i = 0; i < [hashType digestSize]; i++) { - uint8_t c = clientKey[i] ^ clientSignature[i]; - [tmpArray addItem: &c]; - } - - // Add p= - [ret addItem: ","]; - [ret addNItems: 2 - fromCArray: "p="]; - tmpString = [tmpArray stringByBase64Encoding]; - [ret addNItems: [tmpString cStringLength] - fromCArray: [tmpString cString]]; - - [ret retain]; - [pool release]; - pool = nil; - - return [ret autorelease]; - } @finally { - [pool release]; - } + hash = [[[hashType alloc] init] autorelease]; + ret = [OFDataArray dataArrayWithItemSize: 1]; + authMessage = [OFDataArray dataArrayWithItemSize: 1]; + + OFString *chal = [OFString stringWithCString: [challenge cArray] + length: [challenge count] * + [challenge itemSize]]; + + for (OFString *comp in [chal componentsSeparatedByString: @","]) { + OFString *entry = [comp substringFromIndex: 2 + toIndex: [comp length]]; + + if ([comp hasPrefix: @"r="]) { + if (![entry hasPrefix: cNonce]) + @throw [XMPPAuthFailedException + newWithClass: isa + connection: nil + reason: @"Received wrong nonce"]; + + sNonce = entry; + } else if ([comp hasPrefix: @"s="]) + salt = [OFDataArray + dataArrayWithBase64EncodedString: entry]; + else if ([comp hasPrefix: @"i="]) + iterCount = [entry decimalValue]; + } + + // Add c= + // XXX: No channel binding for now + tmpArray = [OFDataArray dataArrayWithItemSize: 1]; + [tmpArray addNItems: [GS2Header cStringLength] + fromCArray: [GS2Header cString]]; + tmpString = [tmpArray stringByBase64Encoding]; + [ret addNItems: 2 + fromCArray: "c="]; + [ret addNItems: [tmpString cStringLength] + fromCArray: [tmpString cString]]; + + // Add r= + [ret addItem: ","]; + [ret addNItems: 2 + fromCArray: "r="]; + [ret addNItems: [sNonce cStringLength] + fromCArray: [sNonce cString]]; + + tmpArray = [OFDataArray dataArrayWithItemSize: 1]; + [tmpArray addNItems: [password cStringLength] + fromCArray: [password cString]]; + + /* + * IETF RFC 5802: + * SaltedPassword := Hi(Normalize(password), salt, i) + */ + saltedPassword = [self _hiWithData: tmpArray + salt: salt + iterationCount: iterCount]; + + /* + * IETF RFC 5802: + * AuthMessage := client-first-message-bare + "," + + * server-first-message + "," + + * client-final-message-without-proof + */ + [authMessage addNItems: [clientFirstMessageBare cStringLength] + fromCArray: [clientFirstMessageBare cString]]; + [authMessage addItem: ","]; + [authMessage addNItems: [challenge count] * [challenge itemSize] + fromCArray: [challenge cArray]]; + [authMessage addItem: ","]; + [authMessage addNItems: [ret count] + fromCArray: [ret cArray]]; + + /* + * IETF RFC 5802: + * ClientKey := HMAC(SaltedPassword, "Client Key") + */ + tmpArray = [OFDataArray dataArrayWithItemSize: 1]; + [tmpArray addNItems: 10 + fromCArray: "Client Key"]; + clientKey = [self _HMACWithKey: saltedPassword + data: tmpArray]; + + /* + * IETF RFC 5802: + * StoredKey := H(ClientKey) + */ + [hash updateWithBuffer: (void*) clientKey + ofSize: [hashType digestSize]]; + tmpArray = [OFDataArray dataArrayWithItemSize: 1]; + [tmpArray addNItems: [hashType digestSize] + fromCArray: [hash digest]]; + + /* + * IETF RFC 5802: + * ClientSignature := HMAC(StoredKey, AuthMessage) + */ + clientSignature = [self _HMACWithKey: tmpArray + data: authMessage]; + + /* + * IETF RFC 5802: + * ServerKey := HMAC(SaltedPassword, "Server Key") + */ + tmpArray = [OFDataArray dataArrayWithItemSize: 1]; + [tmpArray addNItems: 10 + fromCArray: "Server Key"]; + serverKey = [self _HMACWithKey: saltedPassword + data: tmpArray]; + + /* + * IETF RFC 5802: + * ServerSignature := HMAC(ServerKey, AuthMessage) + */ + tmpArray = [OFDataArray dataArrayWithItemSize: 1]; + [tmpArray addNItems: [hashType digestSize] + fromCArray: serverKey]; + serverSignature = [[OFDataArray alloc] initWithItemSize: 1]; + [serverSignature addNItems: [hashType digestSize] + fromCArray: [self _HMACWithKey: tmpArray + data: authMessage]]; + + /* + * IETF RFC 5802: + * ClientProof := ClientKey XOR ClientSignature + */ + tmpArray = [OFDataArray dataArrayWithItemSize: 1]; + for (i = 0; i < [hashType digestSize]; i++) { + uint8_t c = clientKey[i] ^ clientSignature[i]; + [tmpArray addItem: &c]; + } + + // Add p= + [ret addItem: ","]; + [ret addNItems: 2 + fromCArray: "p="]; + tmpString = [tmpArray stringByBase64Encoding]; + [ret addNItems: [tmpString cStringLength] + fromCArray: [tmpString cString]]; + + [ret retain]; + [pool release]; + + return [ret autorelease]; } - (void)parseServerFinalMessage: (OFDataArray*)message { OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init]; - @try { - OFString *mess = [OFString - stringWithCString: [message cArray] - length: [message count] * [message itemSize]]; - - OFString *value = [mess substringFromIndex: 2 - toIndex: [mess length]]; - - if ([mess hasPrefix: @"v="]) { - if ([value compare: - [serverSignature stringByBase64Encoding]]) - @throw [XMPPAuthFailedException - newWithClass: isa - connection: nil - reason: - @"Received wrong ServerSignature"]; - } else - @throw [XMPPAuthFailedException newWithClass: isa - connection: nil - reason: value]; - } @finally { - [pool release]; - } + OFString *mess = [OFString stringWithCString: [message cArray] + length: [message count] * + [message itemSize]]; + OFString *value = [mess substringFromIndex: 2 + toIndex: [mess length]]; + + if ([mess hasPrefix: @"v="]) { + if (![value isEqual: [serverSignature stringByBase64Encoding]]) + @throw [XMPPAuthFailedException + newWithClass: isa + connection: nil + reason: @"Received wrong ServerSignature"]; + } else + @throw [XMPPAuthFailedException newWithClass: isa + connection: nil + reason: value]; + + [pool release]; } @end ADDED src/arc4random_uniform.m Index: src/arc4random_uniform.m ================================================================== --- src/arc4random_uniform.m +++ src/arc4random_uniform.m @@ -0,0 +1,76 @@ +/* + * Copyright (c) 1996, David Mazieres + * Copyright (c) 2008, Damien Miller + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +/* + * Arc4 random number generator for OpenBSD. + * + * This code is derived from section 17.1 of Applied Cryptography, + * second edition, which describes a stream cipher allegedly + * compatible with RSA Labs "RC4" cipher (the actual description of + * which is a trade secret). The same algorithm is used as a stream + * cipher called "arcfour" in Tatu Ylonen's ssh package. + * + * RC4 is a registered trademark of RSA Laboratories. + */ + +#include +#include + +/* + * Calculate a uniformly distributed random number less than upper_bound + * avoiding "modulo bias". + * + * Uniformity is achieved by generating new random numbers until the one + * returned is outside the range [0, 2**32 % upper_bound). This + * guarantees the selected random number will be inside + * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound) + * after reduction modulo upper_bound. + */ +uint32_t +arc4random_uniform(uint32_t upper_bound) +{ + uint32_t r, min; + + if (upper_bound < 2) + return 0; + +#if (ULONG_MAX > 0xffffffffUL) + min = 0x100000000UL % upper_bound; +#else + /* Calculate (2**32 % upper_bound) avoiding 64-bit math */ + if (upper_bound > 0x80000000) + min = 1 + ~upper_bound; /* 2**32 - upper_bound */ + else { + /* (2**32 - (x * 2)) % x == 2**32 % x when x <= 2**31 */ + min = ((0xffffffff - (upper_bound * 2)) + 1) % upper_bound; + } +#endif + + /* + * This could theoretically loop forever but each retry has + * p > 0.5 (worst case, usually far better) of selecting a + * number inside the range we need, so it should rarely need + * to re-roll. + */ + for (;;) { + r = arc4random(); + if (r >= min) + break; + } + + return r % upper_bound; +}