[SOLVED] Shuffle in Bash

Lucien Lachance · 05-14-2013, 09:47 AM

Hi, I've been looking into making a shuffle algorithm more secure that I've written in Bash. I wanted to know how can I make this more random? I've tried to avoid the random bias by using a range, but are there other methods I should be aware of? Here's my code:

Code:

myShuffle() {

local len i j

len=${#myPasswd[@]}

  for (( i=len-1; i > 0; i-- )); do
    while (( (j=$RANDOM) < 32768 % (i+1) )); do :; done;
      j=$(( j % (i+1) ))
      temp=${myPasswd[i]}
      myPasswd[i]=${myPasswd[j]}
      myPasswd[j]=$temp
  done
}

jlinkels · 05-14-2013, 01:07 PM

Please use [ CODE] .. [/CODE] tags around your code. They are generated by pressing the hash (#) in the menu bar of the edit window.

Have a check at this http://tldp.org/LDP/abs/html/randomvar.html

jlinkels

Kustom42 · 05-14-2013, 01:09 PM

Yes, you can easily use /dev/urandom for this. Here is some info and examples:

http://man7.org/linux/man-pages/man4/random.4.html

onebuck · 05-14-2013, 01:44 PM

Moved: This thread is more suitable in <Programming> and has been moved accordingly to help your thread/question get the exposure it deserves.

Lucien Lachance · 05-14-2013, 03:24 PM

Thanks for showing me /dev/urandom I'll be sure to check that out.

konsolebox · 05-16-2013, 07:07 AM

You could try this concept. Can't explain much but please try to understand the code. I believe this is secure enough unless there's something ultra-intelligent light-speed tracer stalking [within] your machine.

Code:

#!/bin/bash

CHARS=(0 1 2 3 4 5 6 7 8 9 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z a b c d e f g h i j k l m n o p q r s t u v w x y z)
CHARS_COUNT=${#CHARS[@]}
PASSWORD_LENGTH=8

PASSWORD=''
for (( I = 1; I <= PASSWORD_LENGTH; ++I )); do
    PASSWORD=${PASSWORD}${CHARS[RANDOM % CHARS_COUNT]}
done

echo "Password: $PASSWORD"

You could add more characters to CHARS, and/or customize PASSWORD_LENGTH if you like. Of course the output could be tapped but that's a different issue and no longer about the strength of the generation of the password.

linosaurusroot · 05-16-2013, 08:52 AM

http://en.wikipedia.org/wiki/Fisher%...3Yates_shuffle -- better than pairwise swaps

sundialsvcs · 05-16-2013, 09:30 AM

Quote:

Originally Posted by linosaurusroot

http://en.wikipedia.org/wiki/Fisher%...3Yates_shuffle -- better than pairwise swaps

Furthermore, it seems to me that the earlier versions would not necessarily work as intended. But I'm baffled to wonder why one would do such a thing, anyway, in Bash! (There are plenty of "real" programming languages at your fingertips ...)

The algorithm is developed as follows:

The "common sense version" is that you start with a deck of 52 cards at the left hand, and an empty pile at the right. Select a card at random from the left, remove it from the pile, and put it on the top of the pile at right. Repeat this 52 times and you're done.
The "clever realization" is that, since there are always exactly 52 cards, you don't actually need two piles. It is equivalent to select a card at-random and exchange it with the card at a cursor-position [52 downto 2]: the "left-hand pile" consists of those cards at-or-below the cursor position, while the "right-hand pile" systematically accumulates at-and-below the cursor.
The algorithm is thorough and instantaneous because there is always a card to choose from, and always a place to put it. There's no possibility that a card would be selected twice, or not selected at all.

But why, oh why, would you do it in Bash?

konsolebox · 05-16-2013, 09:50 AM

Quote:

Originally Posted by linosaurusroot

http://en.wikipedia.org/wiki/Fisher%...3Yates_shuffle -- better than pairwise swaps

That could be done in Bash but I don't see how such an algorithm that shuffles contents could give difference with the strength of password generation.

Lucien Lachance · 05-16-2013, 01:10 PM

Yeah, I know I could've easily have done this in Python, but I really wanted to see how a generator was built. A lot of the times whenever I've used an algorithm to sort elements I've never put much thought into how secure or how "random" rand() really was until now. Plus, I'm kind of getting into security and this is something I've always wanted handy whenever I'm in Vim and need to a good password for an application.

konsolebox · 05-16-2013, 05:52 PM

Quote:

Originally Posted by Lucien Lachance

I've never put much thought into how secure or how "random" rand() really was until now. Plus, I'm kind of getting into security and this is something I've always wanted handy whenever I'm in Vim and need to a good password for an application.

Yet again how would the randomness of rand() be really helpful? It's not as if something would be trying to "guess-trace" it.

Btw, how would you think the script I posted contribute to your requirement?

Beryllos · 05-16-2013, 08:03 PM

I think I missed the point of shuffling. If all you need is a random string, you could do this, for example:

Code:

tony> pass=`head /dev/urandom | tr -dc [:alnum:] | head -c 10`
tony> echo $pass
dFq166jIi1

Are you thinking it will be even more random if you shuffle the bytes?

Lucien Lachance · 05-17-2013, 09:45 PM

Quote:

Originally Posted by konsolebox

Yet again how would the randomness of rand() be really helpful? It's not as if something would be trying to "guess-trace" it.

Btw, how would you think the script I posted contribute to your requirement?

Yes, it did actually. I declared an array using this approach:

Code:

password=( {a..z} {A..Z} {0..9} )

Is there a way I can encapsulate special characters much like the {a..z} expansion that's specifically for special characters?

konsolebox · 05-18-2013, 09:24 AM

For bash alone I don't think there's a way, but for other commands like tput perhaps, perhaps.
Try to find a command that prints the characters of [:graph:] or [:punct:], or perhaps other classes as well as interpreted in regex/glob parsers like grep.

Lucien Lachance · 05-18-2013, 01:41 PM

I'll look into it thanks for the help as well, I really appreciate it.