random generation

Post new topic   Reply to topic    DD-WRT Forum Index -> Contributions Upload
Author Message
JediMaster666
DD-WRT User


Joined: 04 Apr 2017
Posts: 56

PostPosted: Sun Jun 26, 2022 0:23    Post subject: random generation Reply with quote
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.
Sponsor
JediMaster666
DD-WRT User


Joined: 04 Apr 2017
Posts: 56

PostPosted: Wed Jul 06, 2022 20:11    Post subject: Reply with quote
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: 1020
Location: Hung Hom, Hong Kong

PostPosted: Tue Jul 26, 2022 12:05    Post subject: Re: random generation Reply with quote
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)

May the Force and farces be with you! Live long and prosper!

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
Display posts from previous:    Page 1 of 1
Post new topic   Reply to topic    DD-WRT Forum Index -> Contributions Upload All times are GMT

Navigation

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You cannot download files in this forum