`On Oct 28, 2001  20:57 -0300, Horst von Brand wrote:> Andreas Dilger <adilger@turbolabs.com> said:> > OK, my bad.  At least the random variable-name cleanups let you SEE where> > we are supposed to be using word sizes and byte sizes.  Even you were> > confused about it ;-)> > I have now seen various bits and pieces about this flying around. To get it> right will be hard, as over/under estimates will show up only under unusual> circumstances; and as you _can't_ really know how much "entropy" there> should be, testing this is very hard.  So the only way to get it right is> make it "obviously" right.Yes, I have suspected the same thing.  When testing these changes, I almostalways got 9-12 bits of entropy per keypress, and hundreds of bits for amouse movement.  Granted, it may be reasonable given that I have a TSC,which implies nearly random low order bits, but you would think that mouseinterrupts are at a fairly standard rate, so should have low entropy?I left discussion about the actual entropy DATA out of my patch, andfocussed only on getting the accounting right.  We still "discard" someentropy in places, but it is orders of magnitude smaller than before,and discarding entropy is not a danger, unless you are forced to useless-secure data as a result of not having enough entropy.> How hard would it be to change the API to talk _all_ in the same units, be> it bits, bytes, words, or whatever? I believe bits or bytes would be best,> as word sizes differ. Bytes have the advantage that a simple sizeof() will> give size in bytes for any random variable.Not too hard (basic patch below).  This has the drawback of passing abyte count to add_entropy(), but still using a word array for values.It wouldn't be too hard to change add_entropy() to accept a byte array(which we cast internally to a word array, don't really care about endianissues here), and then do something* with any extra bytes.  As it is,add_entropy() "uses" the unset bytes at the end of the last word if weare called from random_write().  We also can't make credit_entropy_store()use bytes as a parameter, so we haven't totally fixed the problem.(*) I don't know enough about the hash functions to know how to add a    few odd bytes into the store in a useful and safe way.  We don't    really want to discard them either - think if a user-space random    daemon on an otherwise entropy-free system only writes one byte at    a time...The second patch (incremental to the first) changes poolwords to poolbytesin all places, but still doesn't fix add_entropy() to handle a byte array asinput.Cheers, Andreas==========================================================================--- linux.orig/drivers/char/random.c	Thu Oct 25 03:04:34 2001+++ linux/drivers/char/random.c	Sun Oct 28 21:28:23 2001@@ -557,13 +553,13 @@  * it's cheap to do so and helps slightly in the expected case where  * the entropy is concentrated in the low-order bits.  */-static void add_entropy_words(struct entropy_store *r, const __u32 *in,-			      int nwords)+static void add_entropy(struct entropy_store *r, const __u32 *in, int nbytes) { 	static __u32 const twist_table = { 		         0, 0x3b6e20c8, 0x76dc4190, 0x4db26158, 		0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278 }; 	unsigned i;+	int nwords = nbytes / 4; 	int new_rotate; 	int wordmask = r->poolinfo.poolwords - 1; 	__u32 w;@@ -693,7 +689,7 @@ 							sec_random_state; 			max_entropy = r->poolinfo.POOLBITS; 		}-		add_entropy_words(r, batch_entropy_pool + 2*batch_tail, 2);+		add_entropy(r, batch_entropy_pool + 2*batch_tail, 8); 		credit_entropy_store(r, batch_entropy_credit[batch_tail]); 		batch_tail = (batch_tail+1) & (batch_max-1); 	}@@ -1245,24 +1241,24 @@  	if (r->entropy_count < nbytes * 8 && 	    r->entropy_count < r->poolinfo.POOLBITS) {-		int nwords = min(r->poolinfo.poolwords - r->entropy_count/32,-				 sizeof(tmp) / 4);+		int cbytes = min(r->poolinfo.POOLBYTES - r->entropy_count/8,+				 sizeof(tmp));  		DEBUG_ENT("xfer %d from primary to %s (have %d, need %d)\n",-			  nwords * 32,+			  cbytes * 8, 			  r == sec_random_state ? "secondary" : "unknown", 			  r->entropy_count, nbytes * 8); -		extract_entropy(random_state, tmp, nwords, 0);-		add_entropy_words(r, tmp, nwords);-		credit_entropy_store(r, nwords * 32);+		extract_entropy(random_state, tmp, cbytes, 0);+		add_entropy(r, tmp, cbytes);+		credit_entropy_store(r, cbytes * 8); 	} 	if (r->extract_count > 1024) { 		DEBUG_ENT("reseeding %s with %d from primary\n", 			  r == sec_random_state ? "secondary" : "unknown", 			  sizeof(tmp) * 8); 		extract_entropy(random_state, tmp, sizeof(tmp), 0);-		add_entropy_words(r, tmp, sizeof(tmp) / 4);+		add_entropy(r, tmp, sizeof(tmp)); 		r->extract_count = 0; 	} }@@ -1343,7 +1339,7 @@ 		 */ 		for (i = 0, x = 0; i < r->poolinfo.poolwords; i += 16, x+=2) { 			HASH_TRANSFORM(tmp, r->pool+i);-			add_entropy_words(r, &tmp[x%HASH_BUFFER_SIZE], 1);+			add_entropy(r, &tmp[x%HASH_BUFFER_SIZE], 4); 		} 		 		/*@@ -1418,7 +1414,7 @@ 	do_gettimeofday(&tv); 	words = tv.tv_sec; 	words = tv.tv_usec;-	add_entropy_words(r, words, 2);+	add_entropy(r, words, sizeof(words));  	/* 	 *	This doesn't lock system.utsname. However, we are generating@@ -1427,7 +1423,7 @@ 	p = (char *) &system_utsname; 	for (i = sizeof(system_utsname) / sizeof(words); i; i--) { 		memcpy(words, p, sizeof(words));-		add_entropy_words(r, words, sizeof(words)/4);+		add_entropy(r, words, sizeof(words)); 		p += sizeof(words); 	} }@@ -1596,7 +1591,7 @@ 		c -= bytes; 		p += bytes; -		add_entropy_words(random_state, buf, (bytes + 3) / 4);+		add_entropy(random_state, buf, bytes); 	} 	if (p == buffer) { 		return (ssize_t)ret;@@ -1747,8 +1742,8 @@ 	if ((ret = create_entropy_store(poolsize, &new_store))) 		return ret; -	add_entropy_words(new_store, random_state->pool,-			  random_state->poolinfo.poolwords);+	add_entropy(new_store, random_state->pool,+		    random_state->poolinfo.POOLBYTES); 	credit_entropy_store(new_store, random_state->entropy_count);  	sysctl_init_random(new_store);============================================================================--- linux/drivers/char/random.c~	Sun Oct 28 21:28:23 2001+++ linux/drivers/char/random.c	Sun Oct 28 21:53:46 2001@@ -279,57 +279,56 @@ static int random_write_wakeup_thresh = 128;  /*- * A pool of size .poolwords is stirred with a primitive polynomial- * of degree .poolwords over GF(2).  The taps for various sizes are+ * A pool of size .poolbytes is stirred with a primitive polynomial+ * of degree .poolbytes over GF(2).  The taps for various sizes are  * defined below.  They are chosen to be evenly spaced (minimum RMS  * distance from evenly spaced; the numbers in the comments are a  * scaled squared error sum) except for the last tap, which is 1 to  * get the twisting happening as fast as possible.  */ static struct poolinfo {-	int	poolwords;+	int	poolbytes; 	int	tap1, tap2, tap3, tap4, tap5; } poolinfo_table[] = { 	/* x^2048 + x^1638 + x^1231 + x^819 + x^411 + x + 1  -- 115 */-	{ 2048,	1638,	1231,	819,	411,	1 },+	{ 16384, 1638,	1231,	819,	411,	1 },  	/* x^1024 + x^817 + x^615 + x^412 + x^204 + x + 1 -- 290 */-	{ 1024,	817,	615,	412,	204,	1 },+	{ 8192,	817,	615,	412,	204,	1 }, #if 0				/* Alternate polynomial */ 	/* x^1024 + x^819 + x^616 + x^410 + x^207 + x^2 + 1 -- 115 */-	{ 1024,	819,	616,	410,	207,	2 },+	{ 8192,	819,	616,	410,	207,	2 }, #endif  	/* x^512 + x^411 + x^308 + x^208 + x^104 + x + 1 -- 225 */-	{ 512,	411,	308,	208,	104,	1 },+	{ 4096,	411,	308,	208,	104,	1 }, #if 0				/* Alternates */ 	/* x^512 + x^409 + x^307 + x^206 + x^102 + x^2 + 1 -- 95 */-	{ 512,	409,	307,	206,	102,	2 },+	{ 4096,	409,	307,	206,	102,	2 }, 	/* x^512 + x^409 + x^309 + x^205 + x^103 + x^2 + 1 -- 95 */-	{ 512,	409,	309,	205,	103,	2 },+	{ 4096,	409,	309,	205,	103,	2 }, #endif  	/* x^256 + x^205 + x^155 + x^101 + x^52 + x + 1 -- 125 */-	{ 256,	205,	155,	101,	52,	1 },+	{ 2048,	205,	155,	101,	52,	1 },  	/* x^128 + x^103 + x^76 + x^51 +x^25 + x + 1 -- 105 */-	{ 128,	103,	76,	51,	25,	1 },+	{ 1024,	103,	76,	51,	25,	1 }, #if 0	/* Alternate polynomial */ 	/* x^128 + x^103 + x^78 + x^51 + x^27 + x^2 + 1 -- 70 */-	{ 128,	103,	78,	51,	27,	2 },+	{ 1024,	103,	78,	51,	27,	2 }, #endif  	/* x^64 + x^52 + x^39 + x^26 + x^14 + x + 1 -- 15 */-	{ 64,	52,	39,	26,	14,	1 },+	{ 512,	52,	39,	26,	14,	1 },  	/* x^32 + x^26 + x^20 + x^14 + x^7 + x + 1 -- 15 */-	{ 32,	26,	20,	14,	7,	1 },+	{ 256,	26,	20,	14,	7,	1 },  	{ 0,	0,	0,	0,	0,	0 }, }; -#define POOLBITS	poolwords*32-#define POOLBYTES	poolwords*4+#define POOLBITS	poolbytes*8  /*  * For the purposes of better mixing, we use the CRC-32 polynomial as@@ -496,17 +495,16 @@ { 	struct	entropy_store	*r; 	struct	poolinfo	*p;-	int	poolwords;+	int	poolbytes; -	poolwords = (size + 3) / 4; /* Convert bytes->words */-	/* The pool size must be a multiple of 16 32-bit words */-	poolwords = ((poolwords + 15) / 16) * 16; +	/* The pool size must be a multiple of 16 32-bit words (64 bytes) */+	poolbytes = ((poolbytes + 63) / 64) * 64;  -	for (p = poolinfo_table; p->poolwords; p++) {-		if (poolwords == p->poolwords)+	for (p = poolinfo_table; p->poolbytes; p++) {+		if (poolbytes == p->poolbytes) 			break; 	}-	if (p->poolwords == 0)+	if (p->poolbytes == 0) 		return -EINVAL;  	r = kmalloc(sizeof(struct entropy_store), GFP_KERNEL);@@ -516,12 +514,12 @@ 	memset (r, 0, sizeof(struct entropy_store)); 	r->poolinfo = *p; -	r->pool = kmalloc(POOLBYTES, GFP_KERNEL);+	r->pool = kmalloc(poolbytes, GFP_KERNEL); 	if (!r->pool) { 		kfree(r); 		return -ENOMEM; 	}-	memset(r->pool, 0, POOLBYTES);+	memset(r->pool, 0, poolbytes); 	*ret_bucket = r; 	return 0; }@@ -533,7 +531,7 @@ 	r->entropy_count = 0; 	r->input_rotate = 0; 	r->extract_count = 0;-	memset(r->pool, 0, r->poolinfo.POOLBYTES);+	memset(r->pool, 0, r->poolinfo.poolbytes); }  static void free_entropy_store(struct entropy_store *r)@@ -561,7 +559,7 @@ 	unsigned i; 	int nwords = nbytes / 4; 	int new_rotate;-	int wordmask = r->poolinfo.poolwords - 1;+	int wordmask = r->poolinfo.poolbytes * 4 - 1; 	__u32 w;  	while (nwords--) {@@ -1241,7 +1239,7 @@  	if (r->entropy_count < nbytes * 8 && 	    r->entropy_count < r->poolinfo.POOLBITS) {-		int cbytes = min(r->poolinfo.POOLBYTES - r->entropy_count/8,+		int cbytes = min(r->poolinfo.poolbytes - r->entropy_count/8, 				 sizeof(tmp));  		DEBUG_ENT("xfer %d from primary to %s (have %d, need %d)\n",@@ -1274,7 +1272,8 @@  * extracting entropy from the secondary pool, and can refill from the  * primary pool if needed.  *- * Note: extract_entropy() assumes that .poolwords is a multiple of 16 words.+ * Note: extract_entropy() assumes that .poolbytes is a multiple of+ *       16 32-bit words (64 bytes).  */ static ssize_t extract_entropy(struct entropy_store *r, void * buf, 			       size_t nbytes, int flags)@@ -1337,7 +1336,7 @@ 		 * attempts to find previous ouputs), unless the hash 		 * function can be inverted. 		 */-		for (i = 0, x = 0; i < r->poolinfo.poolwords; i += 16, x+=2) {+		for (i = 0, x = 0; i < r->poolinfo.poolbytes; i += 64, x+=2) { 			HASH_TRANSFORM(tmp, r->pool+i); 			add_entropy(r, &tmp[x%HASH_BUFFER_SIZE], 4); 		}@@ -1635,13 +1634,14 @@ 		ent_count = random_state->entropy_count; 		if (put_user(ent_count, p++) || 		    get_user(size, p) ||-		    put_user(random_state->poolinfo.poolwords, p++))+		    put_user(random_state->poolinfo.poolbytes / 4, p++)) 			return -EFAULT;+		size *= 4; 		if (size < 0) 			return -EINVAL;-		if (size > random_state->poolinfo.poolwords)-			size = random_state->poolinfo.poolwords;-		if (copy_to_user(p, random_state->pool, size * 4))+		if (size > random_state->poolinfo.poolbytes)+			size = random_state->poolinfo.poolbytes;+		if (copy_to_user(p, random_state->pool, size)) 			return -EFAULT; 		return 0; 	case RNDADDENTROPY:@@ -1743,7 +1743,7 @@ 		return ret;  	add_entropy(new_store, random_state->pool,-		    random_state->poolinfo.POOLBYTES);+		    random_state->poolinfo.poolbytes); 	credit_entropy_store(new_store, random_state->entropy_count);  	sysctl_init_random(new_store);@@ -1758,11 +1758,11 @@ { 	int	ret; -	sysctl_poolsize = random_state->poolinfo.POOLBYTES;+	sysctl_poolsize = random_state->poolinfo.poolbytes;  	ret = proc_dointvec(table, write, filp, buffer, lenp); 	if (ret || !write ||-	    (sysctl_poolsize == random_state->poolinfo.POOLBYTES))+	    (sysctl_poolsize == random_state->poolinfo.poolbytes)) 		return ret;  	return change_poolsize(sysctl_poolsize);@@ -1774,7 +1774,7 @@ { 	int	len; 	-	sysctl_poolsize = random_state->poolinfo.POOLBYTES;+	sysctl_poolsize = random_state->poolinfo.poolbytes;  	/* 	 * We only handle the write case, since the read case gets@@ -1789,7 +1789,7 @@ 			return -EFAULT; 	} -	if (sysctl_poolsize != random_state->poolinfo.POOLBYTES)+	if (sysctl_poolsize != random_state->poolinfo.poolbytes) 		return change_poolsize(sysctl_poolsize);  	return 0;--Andreas Dilgerhttp://sourceforge.net/projects/ext2resize/http://www-mddsp.enel.ucalgary.ca/People/adilger/-To unsubscribe from this list: send the line "unsubscribe linux-kernel" inthe body of a message to majordomo@vger.kernel.orgMore majordomo info at  http://vger.kernel.org/majordomo-info.htmlPlease read the FAQ at  http://www.tux.org/lkml/`
{"ft_lang_label":"__label__en","ft_lang_prob":0.5582916,"math_prob":0.9462638,"size":13035,"snap":"2022-05-2022-21","text_gpt3_token_len":4254,"char_repetition_ratio":0.1799555,"word_repetition_ratio":0.115366206,"special_character_ratio":0.41542003,"punctuation_ratio":0.23001182,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9889842,"pos_list":[0,1,2,3,4,5,6,7,8,9,10],"im_url_duplicate_count":[null,null,null,null,null,null,null,null,null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2022-05-20T20:33:55Z\",\"WARC-Record-ID\":\"<urn:uuid:62ea0c93-5d57-4550-97f4-8e200657eb70>\",\"Content-Length\":\"23905\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:8c7c4cb8-318f-4cfb-8a2f-ab8ad4786e90>\",\"WARC-Concurrent-To\":\"<urn:uuid:8de25b8d-8c6c-49f9-849d-abce545d8fa9>\",\"WARC-IP-Address\":\"104.21.79.90\",\"WARC-Target-URI\":\"https://lkml.org/lkml/2001/10/29/4\",\"WARC-Payload-Digest\":\"sha1:MFTN5RDXBGM6R3MLT7BCNY3JBHR4RBIN\",\"WARC-Block-Digest\":\"sha1:VI6UMINWN33TJESPTRQBR62PQ7577POM\",\"WARC-Identified-Payload-Type\":\"application/xhtml+xml\",\"warc_filename\":\"/cc_download/warc_2022/CC-MAIN-2022-21/CC-MAIN-2022-21_segments_1652662534669.47_warc_CC-MAIN-20220520191810-20220520221810-00562.warc.gz\"}"}