yarrow.c

Vovida 社区开源的 SIP 协议源码

/* -*- Mode: C; c-file-style: "bsd" -*- */

/*
 * Yarrow - Cryptographic Pseudo-Random Number Generator
 * Copyright (c) 2000 Zero-Knowledge Systems, Inc.
 *
 * Permission to use, copy, modify, distribute, and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and that
 * both that copyright notice and this permission notice appear in
 * supporting documentation, and that the name of Zero-Knowledge Systems,
 * Inc. not be used in advertising or publicity pertaining to
 * distribution of the software without specific, written prior
 * permission.  Zero-Knowledge Systems, Inc. makes no representations
 * about the suitability of this software for any purpose.  It is
 * provided "as is" without express or implied warranty.
 * 
 * See the accompanying LICENSE file for more information.
 */

#include <string.h>
#include <limits.h>
#if !defined(WIN32)
#   include <unistd.h>
#   if defined(macintosh)
#       include <Memory.h>
#   else
#       include <netinet/in.h>
#   endif
#endif
#if !defined(YARROW_NO_MATHLIB)
#include <math.h>
#endif

#define YARROW_IMPL
#include "yarrow.h"
#include "yhash.h"
#include "ycipher.h"
#include "ylock.h"
#include "ystate.h"
#include "yexcep.h"

#if defined( YARROW_DEBUG ) || defined( YARROW_TRACE )
#   include <stdio.h>
#endif

#if defined( YARROW_TRACE )
extern int yarrow_verbose;
#define TRACE( x ) do { if (yarrow_verbose) { x } } while (0)
#else
#define TRACE( x ) 
#endif

#if defined(macintosh)
#   define make_big_endian32(x) (x)
#else
#   define make_big_endian32(x) htonl(x)
#endif

#if defined( YARROW_DEBUG )
static void hex_print(FILE* f, const char* var, void* data, size_t size);
#endif

static void block_increment( void* block, const int sz );
#if defined( YARROW_SAVE_STATE )
static int Yarrow_Load_State( Yarrow_CTX *y );
static int Yarrow_Save_State( Yarrow_CTX *y );
#endif

static const byte zero_block[CIPHER_BLOCK_SIZE] = { 0, };

static const char* yarrow_str_error[] = {
    "ok",
    "failed",
    "failed: uninitialized",
    "failed: already initialized",
    "failed: no driver",
    "failed: can't open driver",
    "failed: invalid source id",
    "failed: no more source ids available",
    "failed: invalid argument",
    "failed: insufficient privileges",
    "failed: out of memory",
    "failed: resource exhausted",
    "failed: not enough entropy to generate output",
    "failed: locking error",
    "failed: no state to load",
    "failed: state load or save failed",
    "failed: not implemented"
};

/* calculate limits after initialization */

static void Yarrow_Init_Limits(Yarrow_CTX* y)
{
    double tmp1, tmp2, limit;
    /* max number of gates between reseeds -> exceed this, do forced reseed */

    /* #oututs <= min(2^n, 2^(k/3).Pg) */

    /* => #gates <= min(2^n/Pg, 2^(k/3)) */

    tmp1 = POW_CIPHER_BLOCK_SIZE / y->Pg;
    tmp2 = POW_CIPHER_KEY_SIZE;
    limit = min(tmp1, tmp2);
    if (limit < COUNTER_MAX)
    {
	y->gates_limit = limit;
    }
    else
    {
	y->gates_limit = COUNTER_MAX;
    }
}

/* if the program was forked, the child must not operate on the same
   PRNG state */
#ifdef YARROW_DETECT_FORK

static int Yarrow_detect_fork(Yarrow_CTX *y)
{
    EXCEP_DECL;

    /* this does not work for multi-threaded apps if threads have different
     * pids */
    if ( y->pid != getpid() )
    {
	TRY( Yarrow_Init( y, y->entropyfile ) );
    }

 CATCH:
    EXCEP_RET;
}

#else

#define Yarrow_detect_fork(x) (YARROW_OK)

#endif

static void Yarrow_Make_Seeded( Yarrow_CTX* y )
{
    TRACE( printf( "SEEDED," ); );
    y->seeded = 1;

    /* now we are seeded switch to _THRESH values */

    y->slow_thresh = YARROW_SLOW_THRESH;
    y->fast_thresh = YARROW_FAST_THRESH;
    y->slow_k_of_n_thresh = YARROW_K_OF_N_THRESH;
}

YARROW_DLL
int Yarrow_Init(Yarrow_CTX* y, const char *filename)
{
    EXCEP_DECL;
    int locked = 0;

    if (!y) { THROW( YARROW_BAD_ARG ); }
    TRY( LOCK() );
    locked = 1;

    y->seeded = 0;
    y->saved = 0;

#if defined( YARROW_DETECT_FORK )
    y->pid = getpid();
#endif

    y->entropyfile = filename;
    y->num_sources = 0;
    mem_zero(y->C, sizeof(y->C));
    HASH_Init(&y->pool[YARROW_FAST_POOL]);
    HASH_Init(&y->pool[YARROW_SLOW_POOL]);

    mem_zero(y->K, sizeof(y->K));

    CIPHER_Init(&y->cipher, y->K);
    y->out_left = 0;
    y->out_count = 0;
    y->gate_count = 0;
    y->Pg = YARROW_OUTPUTS_PER_GATE;
    y->Pt[YARROW_FAST_POOL] = YARROW_FAST_PT;
    y->Pt[YARROW_SLOW_POOL] = YARROW_SLOW_PT;
    y->slow_k_of_n = 0;

    /* start with INIT_THRESH values, after seeded, switch to THRESH values */

    y->slow_thresh = YARROW_SLOW_INIT_THRESH;
    y->fast_thresh = YARROW_FAST_INIT_THRESH;
    y->slow_k_of_n_thresh = YARROW_K_OF_N_INIT_THRESH;

    Yarrow_Init_Limits(y);

#if defined( YARROW_SAVE_STATE )
    if ( y->entropyfile != NULL )
    {
	int ret = Yarrow_Load_State( y );
	if ( ret != YARROW_OK && ret != YARROW_NO_STATE )
	{
	    THROW( ret );
	}

	/*  if load suceeded then write new state back immediately
	 */

	/*  Also check that it's not already saved, because the reseed in
	 *  Yarrow_Load_State may trigger a save
	 */

	if ( ret == YARROW_OK && !y->saved )
	{
	    TRY( Yarrow_Save_State( y ) );
	}
    }
#endif

    if ( !y->seeded )
    {
	THROW( YARROW_NOT_SEEDED );
    }

 CATCH:
    if ( locked ) { TRY( UNLOCK() ); }
    EXCEP_RET;
}

YARROW_DLL
int Yarrow_Input( Yarrow_CTX* y, unsigned source_id, 
		  const void* sample, 
		  size_t size, size_t entropy_bits )
{
    EXCEP_DECL;
    int ret;
    int locked = 0;
    Source* source;
    size_t new_entropy;
    size_t estimate;

    if (!y) { THROW( YARROW_BAD_ARG ); }
    TRY( Yarrow_detect_fork( y ) );

    if (source_id >= y->num_sources) { THROW( YARROW_BAD_SOURCE ); }
  
    source = &y->source[source_id];
  
    if(source->pool != YARROW_FAST_POOL && source->pool != YARROW_SLOW_POOL)
    {
	THROW( YARROW_BAD_SOURCE );
    }

    TRY( LOCK() );
    locked = 1;

    /* hash in the sample */

    HASH_Update(&y->pool[source->pool], (const void*)sample, size);
  
    /* only update entropy estimate if pool is not full */

    if ( (source->pool == YARROW_FAST_POOL && 
	  source->entropy[source->pool] < y->fast_thresh) ||
	 (source->pool == YARROW_SLOW_POOL &&
	  source->entropy[source->pool] < y->slow_thresh) )
    {
	new_entropy = min(entropy_bits, size * 8 * YARROW_ENTROPY_MULTIPLIER);
	if (source->estimator)
	{
	    estimate = source->estimator(sample, size);
	    new_entropy = min(new_entropy, estimate);
	}
	source->entropy[source->pool] += new_entropy;
	if ( source->entropy[source->pool] > YARROW_POOL_SIZE )
	{
	    source->entropy[source->pool] = YARROW_POOL_SIZE;
	}

	if (source->pool == YARROW_FAST_POOL)
	{
	    if (source->entropy[YARROW_FAST_POOL] >= y->fast_thresh)
	    {
		ret = Yarrow_Reseed(y, YARROW_FAST_POOL);
		if ( ret != YARROW_OK && ret != YARROW_NOT_SEEDED )
		{
		    THROW( ret );
		}
	    }
	}
	else
	{
	    if (!source->reached_slow_thresh && 
		source->entropy[YARROW_SLOW_POOL] >= y->slow_thresh)
	    {
		source->reached_slow_thresh = 1;
		y->slow_k_of_n++;
		if (y->slow_k_of_n >= y->slow_k_of_n_thresh)
		{
		    y->slow_k_of_n = 0;
		    ret = Yarrow_Reseed(y, YARROW_SLOW_POOL);
		    if ( ret != YARROW_OK && ret != YARROW_NOT_SEEDED )
		    {
			THROW( ret );
		    }
		}
	    }
	}
    }
  
    /* put samples in alternate pools */

    source->pool = (source->pool + 1) % 2;
  
 CATCH:
    if ( locked ) { TRY( UNLOCK() ); }
    EXCEP_RET;
}

YARROW_DLL
int Yarrow_New_Source(Yarrow_CTX* y, unsigned* source_id)
{
    EXCEP_DECL;
    int locked = 0;
    Source* source;

    if (!y) { THROW( YARROW_BAD_ARG ); }

    TRY( LOCK() );
    locked = 1;

    if (y->num_sources + 1 > YARROW_MAX_SOURCES)
    {
	THROW( YARROW_TOO_MANY_SOURCES );
    }

    *source_id = y->num_sources;

    source = &y->source[*source_id];

    source->pool = YARROW_FAST_POOL;
    source->entropy[YARROW_FAST_POOL] = 0;
    source->entropy[YARROW_SLOW_POOL] = 0;
    source->reached_slow_thresh = 0;
    source->estimator = 0;

    y->num_sources++;
CATCH:
    if ( locked ) { TRY( UNLOCK() ); }
    EXCEP_RET;
}

int Yarrow_Register_Source_Estimator(Yarrow_CTX* y, unsigned source_id, 
                                     estimator_fn* fptr)
{
    EXCEP_DECL;
    Source* source;

    if (!y) { THROW( YARROW_BAD_ARG ); }
    if (source_id >= y->num_sources) { THROW( YARROW_BAD_SOURCE ); }

    source = &y->source[source_id];

    source->estimator = fptr;
  
 CATCH:
    EXCEP_RET;
}

static int Yarrow_Output_Block( Yarrow_CTX* y, void* out )
{
    EXCEP_DECL;

    if (!y || !out) { THROW( YARROW_BAD_ARG ); }

    TRACE( printf( "OUT," ); );

    /* perform a gate function after Pg outputs */

    y->out_count++;
    if (y->out_count >= y->Pg)
    {
	y->out_count = 0;
	TRY( Yarrow_Gate( y ) );

	/* require new seed after reaching gates_limit */

	y->gate_count++;
	if ( y->gate_count >= y->gates_limit )
	{
	    y->gate_count = 0;
	    
	    /* not defined whether to do slow or fast reseed */ 
	    
	    TRACE( printf( "OUTPUT LIMIT REACHED," ); );

	    TRY( Yarrow_Reseed( y, YARROW_SLOW_POOL ) );
	}
    }
  
    /* C <- (C + 1) mod 2^n */

    block_increment( y->C, CIPHER_BLOCK_SIZE );

    /* R <- E_k(C) */

    CIPHER_Encrypt_Block( &y->cipher, y->C, out );

#if defined(YARROW_DEBUG)
    printf("===\n");
    hex_print( stdout, "output: C", y->C, CIPHER_BLOCK_SIZE );
    hex_print( stdout, "output: K", y->K, CIPHER_KEY_SIZE );
    hex_print( stdout, "output: O", out, CIPHER_BLOCK_SIZE );
#endif
 CATCH:
    EXCEP_RET;
}

YARROW_DLL
int Yarrow_Status( Yarrow_CTX* y, int *num_sources, unsigned *source_id,
		   size_t *entropy_bits, size_t *entropy_max )
{
    EXCEP_DECL;
    int num = y->slow_k_of_n_thresh;
    int source = -1;
    int emax = y->slow_thresh;
    size_t entropy = 0;
    unsigned i;

    if (!y) { THROW( YARROW_BAD_ARG ); }
    TRY( Yarrow_detect_fork( y ) );

    if (num_sources) { *num_sources = num; }
    if (source_id) { *source_id = -1; }
    if (entropy_bits) { *entropy_bits = 0; }
    if (entropy_max) { *entropy_max = emax; }