From e541c3126677344291343baf747b62bb8c52e76a Mon Sep 17 00:00:00 2001 From: Gunnar Wrobel Date: Mon, 15 Nov 2010 09:02:58 +0100 Subject: [PATCH] Added a first hashing algorithm (for session based nonce invalidation). --- framework/Nonce/lib/Horde/Nonce.php | 41 ++++++++-- framework/Nonce/lib/Horde/Nonce/Generator.php | 87 +++++++++++++++++++++ framework/Nonce/lib/Horde/Nonce/Hash.php | 83 ++++++++++++++++++++ framework/Nonce/package.xml | 12 ++- .../test/Horde/Nonce/Integration/NonceTest.php | 88 +++++++++++++++++++++- framework/Nonce/test/Horde/Nonce/StoryTestCase.php | 42 ++++++++++- 6 files changed, 341 insertions(+), 12 deletions(-) create mode 100644 framework/Nonce/lib/Horde/Nonce/Generator.php create mode 100644 framework/Nonce/lib/Horde/Nonce/Hash.php diff --git a/framework/Nonce/lib/Horde/Nonce.php b/framework/Nonce/lib/Horde/Nonce.php index a17b89c80..892e50230 100644 --- a/framework/Nonce/lib/Horde/Nonce.php +++ b/framework/Nonce/lib/Horde/Nonce.php @@ -28,13 +28,43 @@ class Horde_Nonce { /** + * The nonce generator. + * + * @var Horde_Nonce_Generator + */ + private $_generator; + + /** + * Hashes the random part of a nonce for storage in the Bloom filter. + * + * @var Horde_Nonce_Hash + */ + private $_hash; + + /** + * Constructor. + * + * @param Horde_Nonce_Hash $hash Hashes the random part of a nonce for + * storage in the Bloom filter. + * @param int $size Size of the random part of the generated + * nonces. + */ + public function __construct( + Horde_Nonce_Generator $generator, + Horde_Nonce_Hash $hash + ) { + $this->_generator = $generator; + $this->_hash = $hash; + } + + /** * Return a nonce. * * @return string The nonce. */ - public function get() + public function create() { - return pack('Nn2', time(), mt_rand(), mt_rand()); + return $this->_generator->create(); } /** @@ -45,12 +75,13 @@ class Horde_Nonce * * @return boolean True if the nonce is still valid. */ - public function isValid($nonce, $timeout) + public function isValid($nonce, $timeout = -1) { - $timestamp = unpack('N', substr($nonce, 0, 4)); - if (array_pop($timestamp) < (time() - $timeout)) { + list($timestamp, $random) = $this->_generator->split($nonce); + if ($timeout > 0 && $timestamp < (time() - $timeout)) { return false; } + return true; } } diff --git a/framework/Nonce/lib/Horde/Nonce/Generator.php b/framework/Nonce/lib/Horde/Nonce/Generator.php new file mode 100644 index 000000000..83b8e61c1 --- /dev/null +++ b/framework/Nonce/lib/Horde/Nonce/Generator.php @@ -0,0 +1,87 @@ + + * @license http://www.fsf.org/copyleft/lgpl.html LGPL + * @link http://pear.horde.org/index.php?package=Nonce + */ + +/** + * Generates nonces. + * + * Copyright 2010 The Horde Project (http://www.horde.org/) + * + * See the enclosed file COPYING for license information (LGPL). If you + * did not receive this file, see http://www.fsf.org/copyleft/lgpl.html. + * + * @category Horde + * @package Nonce + * @author Gunnar Wrobel + * @license http://www.fsf.org/copyleft/lgpl.html LGPL + * @link http://pear.horde.org/index.php?package=Nonce + */ +class Horde_Nonce_Generator +{ + /** + * Size of the random part of the nonce. + * + * @var int + */ + private $_size; + + /** + * Constructor. + * + * @param int $size Size of the random part of the generated nonces (16 bits + * per increment). + */ + public function __construct($size = 1) + { + $this->_size = $size; + } + + /** + * Return a nonce. + * + * @return string The nonce. + */ + public function create() + { + return pack('N', time()) . $this->_createRandom(); + } + + /** + * Return the random part for a nonce. + * + * @return string The random part. + */ + private function _createRandom() + { + $random = ''; + for ($i = 0;$i < $this->_size * 2; $i++) { + $random .= pack('n', mt_rand()); + } + return $random; + } + + /** + * Split a nonce into the timestamp and the random part. + * + * @param string $nonce The nonce to be splitted. + * + * @return array A list of two elements: the timestamp and the random part. + */ + public function split($nonce) + { + $timestamp = unpack('N', substr($nonce, 0, 4)); + return array( + array_pop($timestamp), + unpack('n' . $this->_size * 2, substr($nonce, 4)) + ); + } +} diff --git a/framework/Nonce/lib/Horde/Nonce/Hash.php b/framework/Nonce/lib/Horde/Nonce/Hash.php new file mode 100644 index 000000000..f2c43d2aa --- /dev/null +++ b/framework/Nonce/lib/Horde/Nonce/Hash.php @@ -0,0 +1,83 @@ + + * @license http://www.fsf.org/copyleft/lgpl.html LGPL + * @link http://pear.horde.org/index.php?package=Nonce + */ + +/** + * Hashes the random part of a nonce so that it can be stored in the Bloom + * filter. + * + * Copyright 2010 The Horde Project (http://www.horde.org/) + * + * See the enclosed file COPYING for license information (LGPL). If you + * did not receive this file, see http://www.fsf.org/copyleft/lgpl.html. + * + * @category Horde + * @package Nonce + * @author Gunnar Wrobel + * @license http://www.fsf.org/copyleft/lgpl.html LGPL + * @link http://pear.horde.org/index.php?package=Nonce + */ +class Horde_Nonce_Hash +{ + /** + * Number of hash functions / resulting hash keys. + * + * @var int + */ + private $_keys; + + /** + * Bit length of the hash keys. + * + * @var int + */ + private $_size; + + /** + * Constructor. + * + * @param int $keys Number of resulting hash keys. + * @param int $size Size of the resulting hash keys. + */ + public function __construct($keys = 3, $size = 196) + { + $this->_keys = $keys; + $this->_size = $size; + } + + /** + * Hash the random part of a nonce. + * + * @param array $random The random part of the nonce splitted into two byte segments. + * + * @return array The resulting hash key array. + */ + public function hash(array $random) + { + /** + * Use only 31 bit of randomness as this is sufficient for the hashing + * and avoids troubles with signed integers. + */ + $start = array_pop($random); + $start |= (array_pop($random) & (pow(2, 15) - 1)) << 16; + + $hash = array(); + $hash[0] = $start % 197; + $start = (int) $start / 197; + $hash[1] = $start % 197; + $start = (int) $start / 197; + $hash[2] = $start % 197; + + return $hash; + } +} diff --git a/framework/Nonce/package.xml b/framework/Nonce/package.xml index e4b54a113..43df78071 100644 --- a/framework/Nonce/package.xml +++ b/framework/Nonce/package.xml @@ -29,8 +29,8 @@ wrobel@pardus.de yes - 2010-11-03 - + 2010-11-09 + 0.0.1 0.0.1 @@ -47,6 +47,10 @@ + + + + @@ -78,6 +82,8 @@ + + @@ -95,7 +101,7 @@ alpha alpha - 2010-11-03 + 2010-11-09 LGPL * Initial release. diff --git a/framework/Nonce/test/Horde/Nonce/Integration/NonceTest.php b/framework/Nonce/test/Horde/Nonce/Integration/NonceTest.php index b727d17c6..ce26f287c 100644 --- a/framework/Nonce/test/Horde/Nonce/Integration/NonceTest.php +++ b/framework/Nonce/test/Horde/Nonce/Integration/NonceTest.php @@ -38,7 +38,7 @@ extends Horde_Nonce_StoryTestCase /** * @scenario */ - public function aDefaultNonceHasADefinedLengthOfEightBytes() + public function defaultLength() { $this->given('the default nonce setup') ->when('retrieving a nonce') @@ -48,11 +48,95 @@ extends Horde_Nonce_StoryTestCase /** * @scenario */ - public function aNonceWillBeInvalidIfItHasTimedOut() + public function nonceTimeOut() { $this->given('the default nonce setup') ->when('retrieving a nonce') ->and('waiting for two seconds') ->then('the nonce is invalid given a timeout of one second'); } + + /** + * @scenario + */ + public function nonceWithoutTimeout() + { + $this->given('the default nonce setup') + ->when('retrieving a nonce') + ->and('waiting for two seconds') + ->then('the nonce is valid given no timeout'); + } + + /** + * @scenario + */ + public function nonceCounterValue() + { + $this->given('the default nonce generator') + ->when('splitting nonce', 'MABBCCDD') + ->then('the extracted counter value (here: timestamp) is', 1296122434); + } + + /** + * @scenario + */ + public function nonceRandomValue() + { + $this->given('the default nonce generator') + ->when('splitting nonce', 'MABBCCDD') + ->then('the extracted random part matches', array(1 => 17219, 2 => 17476)); + } + + /** + * @scenario + */ + public function nonceHashes() + { + $this->given('the default hash setup') + ->when('hashing nonce', 'MABBCCDD') + ->then('the hash representation provides the hashes', 62, 165, 118); + } + + /** + * @scenario + */ + public function emptyFilter() + { + $this->given('the default filter setup') + ->when('testing whether a nonce is unused if it has the following counter and hash values', 50, 3, 10, 47) + ->then('the nonce is unused'); + } + + /** + * @scenario + */ + public function lowerCounter() + { + $this->given('the default filter setup') + ->and('the following counter and hash values are marked', 10, 3, 10, 47) + ->when('testing whether a nonce is unused if it has the following counter and hash values', 50, 3, 10, 47) + ->then('the nonce is unused'); + } + + /** + * @scenario + */ + public function unusedElement() + { + $this->given('the default filter setup') + ->and('the following counter and hash values are marked', 100, 3, 11, 47) + ->when('testing whether a nonce is unused if it has the following counter and hash values', 50, 3, 10, 47) + ->then('the nonce is unused'); + } + + /** + * @scenario + */ + public function used() + { + $this->given('the default filter setup') + ->and('the following counter and hash values are marked', 100, 3, 10, 47) + ->when('testing whether a nonce is unused if it has the following counter and hash values', 50, 3, 10, 47) + ->then('the nonce is used'); + } } \ No newline at end of file diff --git a/framework/Nonce/test/Horde/Nonce/StoryTestCase.php b/framework/Nonce/test/Horde/Nonce/StoryTestCase.php index 306f09958..d9ad32091 100644 --- a/framework/Nonce/test/Horde/Nonce/StoryTestCase.php +++ b/framework/Nonce/test/Horde/Nonce/StoryTestCase.php @@ -43,7 +43,15 @@ extends PHPUnit_Extensions_Story_TestCase { switch($action) { case 'the default nonce setup': - $world['nonce_handler'] = new Horde_Nonce(); + $world['nonce_handler'] = new Horde_Nonce( + new Horde_Nonce_Generator(), + new Horde_Nonce_Hash() + ); + break; + case 'the default hash setup': + $world['nonce_hash'] = new Horde_Nonce_Hash(); + case 'the default nonce generator': + $world['nonce_generator'] = new Horde_Nonce_Generator(); break; default: return $this->notImplemented($action); @@ -63,11 +71,20 @@ extends PHPUnit_Extensions_Story_TestCase { switch($action) { case 'retrieving a nonce': - $world['nonce'] = $world['nonce_handler']->get(); + $world['nonce'] = $world['nonce_handler']->create(); break; case 'waiting for two seconds': sleep(2); break; + case 'splitting nonce': + list($timestamp, $random) = $world['nonce_generator']->split($arguments[0]); + $world['timestamp'] = $timestamp; + $world['random'] = $random; + break; + case 'hashing nonce': + list($timestamp, $random) = $world['nonce_generator']->split($arguments[0]); + $world['hashes'] = $world['nonce_hash']->hash($random); + break; default: return $this->notImplemented($action); } @@ -91,6 +108,27 @@ extends PHPUnit_Extensions_Story_TestCase case 'the nonce is invalid given a timeout of one second': $this->assertFalse($world['nonce_handler']->isValid($world['nonce'], 1)); break; + case 'the nonce is valid given no timeout': + $this->assertTrue($world['nonce_handler']->isValid($world['nonce'])); + break; + case 'the extracted counter value (here: timestamp) is': + $this->assertEquals( + $world['timestamp'], + $arguments[0] + ); + break; + case 'the extracted random part matches': + $this->assertEquals( + $world['random'], + $arguments[0] + ); + break; + case 'the hash representation provides the hashes': + $this->assertEquals( + $world['hashes'], + $arguments + ); + break; default: return $this->notImplemented($action); } -- 2.11.0