JediMaster666 DD-WRT User
Joined: 04 Apr 2017 Posts: 56
|
Posted: Sun Jun 26, 2022 0:23 Post subject: random generation |
|
Last week I started working on a solution to a problem with my ISP by randomly generating a new VPN server to connect to. In the course of all of that, I came up with a couple scripts I thought people of this forum might find interesting. First, some background information about randomness and the system tool I'm using. I'll clearly mark the TL;DR section if you want to skip to the code. But if you don't know the limitations of /dev/[u]random, you shouldn't.
-------------------[ TL;DR ]-------------------
Nothing in computing is random enough to be considered random unless its algorithm is seeded with information outside the system. Traditionally, the best way to do this was time measured in nanoseconds. Time is in the system yet not seeded with information of the system. With good modern devices, the clock is only connected to the system. Older/bad systems have to "tick" the clock manually as part of system operation. Either way, this makes it a readily available source for generating numbers. However, we use a stripped down version of Linux so some tools like "date" don't have all their features. While looking for ways around this, I came across a double edged sword.
These days, random numbers are used for cryptography. That makes generating good random numbers more important than ever. Especially on devices that encrypt traffic. Naturally, DD-WRT must have some way of doing this. It turns out there is a system device available but the source of the data it returns (something called "entropy" which is discarded data from the system's analog to digital conversions) comes from a shared pool which can be seen (measured in bytes) with the following command:
Code: | cat /proc/sys/kernel/random/entropy_avail |
The critical thing to know when working with this resource is that it is a shared pool. Some software will have to wait until the pool refreshes before it can continue. The pool never really goes away but it is not considered to be fresh if it has been used before. It only takes seconds to refresh but seconds are a lifetime in terms of computing. Making a process wait that long is not a good idea especially if what it's doing is mission critical like wireless or VPN encryption. The way I access this pool (/dev/urandom) will not wait for the data to be fresh but it still uses the shared pool which might cause undesirable behavior from software that accesses a device that will wait (/dev/random).
For some clarity in terms of the scale I'm talking about, typically testing a number generating algorithm requires you to run it a bunch of times. I like 2 billion because it's a nice even number in the 32 bit integer range. This is the type of thing that would be a bad idea. If you minimize the amount of data you pull and only pull every few seconds, you shouldn't worry too much about over using it.
TL;DR:
abuse /dev/urandom at your own peril
---------------------------------------------------------
rng.sh
-------
If you came to this post looking for an easy script that works like a random(n) call to generate a number from 0 to n-1 that works from n=1 to 2,147,483,647 this is what you want. I added a trick to try and get around the typical problem of bias towards lower numbers. I also left instructions if you want to take that part out.
Code: | #!/bin/sh
# for a passed number n, this script
# returns a number in range 0 to n-1
# works from n=1 to 2,147,483,647
# read 4 bytes as a signed integer
PRE_RNG=`hexdump -e '"%i" "\n"' -n 4 /dev/urandom`
# use logical AND to make sure 32nd bit is always a 0 to remove negative numbers
RNG=`echo "$(( 0x7FFFFFFF & $PRE_RNG ))"`
# expr $RNG % $1
#--------------------------------------------------
# for the quick and dirty method, uncomment the code
# above the line and delete the line and everything below it
#get modulo of generated number
MOD=`expr $RNG % $1`
#see if randomly generated number was odd
ODD=`expr $RNG % 2`
# return the mod if the randomly generated number was odd or if the mod is 0
if [ $ODD == 1 -o $MOD == 0 ]
then
echo $MOD
# subtract the mod from the passed number if RNG was even
else
expr $1 - $MOD
fi
|
rcg.sh
-------
This takes in two arguments. The number of characters to return and a string containing the pool of characters to pick from. In the process of trying to incorporate printf into one of my iterations, I realized I didn't want random numbers. I wanted random characters from 0-9. The best part of this script is that the actual code is only 2 lines. The rest of it is instructions. I haven't seen this anywhere else. If you're interested in having this kind of functionality as part of the project, I can write a cleaner version in C.
Code: | #!/bin/sh
# this script takes two arguments, a count of characters to return and a string of characters to look for
#
# 8 Digits 0-9:
# rcg.sh 8 0123456789
#
# 6 Digits 0-f:
# rcg.sh 6 0123456789abcdef
#
# 4 upper case vowels:
# rcg.sh 4 AEIOUY
#
# 2 vowels of either case
# rcg.sh 2 AEIOUYaeiouy
# head will look for 10 new line characters by default from the system device
# it returns all the information until the 10th '\n'
# this means the amount of data returned is not stattic
# tr will interpret the bytes as ASCII and look for characters that match the passed matching string
# using the script as configured should provide a pool of a pool that is alyways over 15 and reliably over 30
# if you find yourself needing more characters than you're getting back, increase by a factor of 10 and try again
# be mindful that the pool of avalible bytes from the system device is limited
# it is gradually replenished by the system
# the system will pause software that accesses the pool if it is empty
# other software requires this pool to function so emptying it is not advised
# the amount avaluble can be seen with this command: cat /proc/sys/kernel/random/entropy_avail
# stop testing if it gets below 2000
# unless you're spamming reads, you thould be fine
RCG=`head -n 10 /dev/urandom | tr -dc $2`
# returns the requested number of characters from the retrieved buffer
echo "${RCG:0:$1}"
|
rng2.sh
-------
I believe this method to be the best way to generate random numbers. However, it functions poorly as a shell script. I either have to pull a large buffer from the system device or make the system call to read from the device when I want more data. I also have to work in bytes when this should be done with bits. Bit shifting would also make the logarithm math MUCH faster. The math explanation of what makes other methods worse is complicated. However, the math explanation of why this is better is easy. With most methods, you're trying to distill many possibilities into distinct bins which makes bias for or against certain numbers. By reading the minimal number of bits and discarding any results too large, you make each outcome 100% unique which means 0% chance for bias. I might wind up writing this for personal use because I like it so much.
Code: | #!/bin/sh
# for a passed number n, this script
# returns a number in range 0 to n-1
# works from n=1 to 2,147,483,647
# get log base 16 of n - 1
# ( number of hex digits for the max number )
X=`expr $1 - 1`
LOG16_COUNTER="0"
while [ $X -gt 0 ]
do
LOG16_COUNTER=`expr $LOG16_COUNTER + 1`
X=`expr $X / 16`
done
# get log base 2 of the Log16 counter
# ( number of bytes to read at a time )
LOG2_COUNTER="0"
X=$LOG16_COUNTER
while [ $X -gt 0 ]
do
LOG2_COUNTER=`expr $LOG2_COUNTER + 1`
X=`expr $X / 2`
done
# get bytes from the device until you find a random number lower than n
OUT_NUM=$1
OUT_BUFF=`hexdump -e '"%x"' -n 256 /dev/urandom`
while [ $OUT_NUM -ge $1 ]
do
OUT_NUM=`printf "%u" 0x${OUT_BUFF:X:LOG2_COUNTER}`
X=`expr $X + 1`
done
echo $OUT_NUM
|
If ya'll are interested in the C code, I'll definitely put it together. If not, I might just use them as is. |
|
JediMaster666 DD-WRT User
Joined: 04 Apr 2017 Posts: 56
|
Posted: Wed Jul 06, 2022 20:11 Post subject: |
|
As expected, setting up the environment took longer than writing the code. I made a random number generator, random character generator, and random byte (n * 2 hex digits) generator. |
|
mwchang DD-WRT Guru
Joined: 26 Mar 2013 Posts: 1856 Location: Hung Hom, Hong Kong
|
Posted: Tue Jul 26, 2022 12:05 Post subject: Re: random generation |
|
JediMaster666 wrote: | Last week I started working on a solution to a problem with my ISP by randomly generating a new VPN server to connect to. In the course of all of that, I came up with a couple scripts I thought people of this forum might find interesting. First, some background information about randomness and the system tool I'm using. I'll clearly mark the TL;DR section if you want to skip to the code. But if you don't know the limitations of /dev/[u]random, you shouldn't.... |
Out of curiosity, does Busybox's "shuf" command also use /dev/urandom?
I also noticed that there are 3 random devices:
Code: | # ls -l /dev/*ran*
crw-r--r-- 1 root root 10, 183 Jan 1 1970 /dev/hw_random
crw-r--r-- 1 root root 1, 8 Jan 1 1970 /dev/random
crw-r--r-- 1 root root 1, 9 Jan 1 1970 /dev/urandom
|
DD-WRT's Busybox didn't enable "shuf", and "flock" as well.
_________________ Router: Asus RT-N18U (rev. A1)
Drink, Blink, Stretch! Live long and prosper! May the Force and farces be with you!
Facebook: https://www.facebook.com/changmanwai
Website: https://sites.google.com/site/changmw
SETI@Home profile: http://setiathome.berkeley.edu/view_profile.php?userid=211832
GitHub: https://github.com/changmw/changmw |
|