2

Some GNU coreutils utilities like sort and shuf use a file as what effectively serves a seed. Does the size of the file matter?

The recommended way, https://www.gnu.org/software/coreutils/manual/html_node/Random-sources.html, uses an openssl-based method that takes a rather long time.

What if I just used a 6-letter word as below? Does this affect the ability of said utilities to create pseudo-randomness?

shuf -i1-10 --random-source=<(echo durian)

2 Answers 2

4

If you provide a fixed string as the random source, then it will "randomise" in the same way every single time. To prove this, let's test it.

$ printf '%s\n' a b c | shuf --random-source=<(echo durian)
b
c
a

On my system, the output is the same every time I run the command above. (I suspect it might be different depending on the implementation, but it should still be the same every time.) You are hard-coding the randomness, as per this XKCD:

XKCD

It's not really random; it's just producing the same output every time. The size of the fixed-string source is irrelevant. It's still fixed.

There's relevant info in the link you provide relating to the random quality of the random source:

/dev/urandom suffices for most practical uses, but applications requiring high-value or long-term protection of private data may require an alternate data source like /dev/random or /dev/arandom.

The latter two options are "more random" than the first. The implication is that the more random the source, the more random the shuffling. Hence, fixed strings are not particularly robust.

With shuf specifically, the length of the fixed string is relevant. For example, the following fails.

shuf -i1-19 --random-source=<(echo durian)

However, if you restrict output to -n16, it works, but -n17 fails. I tested a few different words and permutations, and as I reduce the number of characters in the source, the maximum -n goes down.

source length     max -n
7                 16
6                 13
5                 10
4                  8
3                  5
2                  3
1                  1
0                  0

I'm not sure of the direct relationship, but presumably additional sorted items (in -n) require more source characters as seeds. Nevertheless, in shuf at least, once you pass this minimum threshold, each additional character makes no difference to the randomness per se. In the above example, if you change the 50th character the output will still be the same.

7
  • Thanks Spearhawk for the detailed and interesting answer. I understand using a fixed string, like in my example, or even the openssl method suggested in the documentation, ensures each invocation is deterministic by providing a seed value. This is by design; making each invocation's result deterministic is useful in some modeling applications. My question, which I might not have explained well, is more concerned about whether the length of the string makes a difference for furnishing randomness in one invocation. For instance, I wouldn't want a shuffle of 1-100 to be more or less sorted.
    – flow2k
    Feb 1, 2019 at 7:08
  • @flow2k I'm not really sure I understand the question. As per my answer: "The size of the fixed-string source is irrelevant. It's still fixed." Does that answer it? In one invocation, length has no relevance. If it's one specific fixed string, then it will have a constant output whether the length is 1 character or a billion.
    – Sparhawk
    Feb 1, 2019 at 8:34
  • No, it does not answer it 😆. Hmm. Are you familiar with the use of a seed value? Per my understanding, this "fix-string source" serves as exactly that.
    – flow2k
    Feb 2, 2019 at 20:33
  • My question is about the length of said "fixed-string source". You say "length has no relevance". It seems it does have some effect; I tried just now shuf -i1-19 --random-source=<(echo durian) and it gave me error, apparently because durian is too short. But I don't know enough about the internals of shuf to understand why.
    – flow2k
    Feb 2, 2019 at 20:36
  • Ah I understand now. Edited.
    – Sparhawk
    Feb 4, 2019 at 4:24
2

Yes, the size matters for shuf: The size must be as big as necessary for randint_genmax() in https://github.com/coreutils/coreutils/blob/master/gl/lib/randint.c to derive all the random numbers the used shuffle algorithm needs (each number may be picked from a specific range). This size depends on both

  • the number of input lines and
  • the byte values in the random source file.

If you change a byte in the random source file it can change how many bytes in total are needed. For example, if a number in the range 0-254 is needed it suffice to read one byte if it happens to be in this range but if the byte is '\xff' (255 as an unsigned 8-bit integer) at least one more byte is needed as well.

This can be used to construct an example that fails even though plenty of bytes are provided:

shuf -i1-10 --random-source=<(echo $'\xff\xff\xff\xff\xff\xff\xff\xff')
shuf: ‘/dev/fd/63’: end of file

Just three bytes 'ab'+newline can be be enough:

shuf -i1-10 --random-source=<(echo ab) | md5sum
742a739ea959851f883ec692d6675cdf  -

To provide a pseudo random source with seed, I didn't find a command line only solution but at least here is a draft solution using bash only (see known issue below):

(1) Helper script seed-and-counter.sh:

#!/bin/bash
SEED="$1"
COUNTER=0
while true; do
    echo $SEED $COUNTER
    COUNTER=$((COUNTER+1))
done

(2) Helper script bin-hash-lines.sh:

#!/bin/bash
echo "$1" | md5sum | cut -c-32 | xxd -r -p

(3) Combine them to produce a reproducible sequence of random bytes:

./seed-and-counter.sh 320 | xargs -d'\n' -n 1 ./bin-hash-lines.sh | hexdump -C | head
00000000  02 56 8b 68 34 78 bd 98  6e 8d 42 d2 cb 7b 8d b4  |.V.h4x..n.B..{..|
00000010  7d d8 23 b9 89 f8 29 5b  6c 51 fb 9f b3 74 1d 03  |}.#...)[lQ...t..|
00000020  bc 1d 62 81 31 0b 5d 82  8c cb 37 4a b8 bc 85 70  |..b.1.]...7J...p|
00000030  88 3d 57 ae ef 77 28 aa  3a cf f7 49 ed 00 37 21  |.=W..w(.:..I..7!|
00000040  45 55 39 94 3f 30 90 49  4f f0 04 d5 1e c5 0c 1e  |EU9.?0.IO.......|
00000050  e4 e8 8e 72 84 58 3c 03  66 e5 bd af fb 87 78 6b  |...r.X<.f.....xk|
00000060  b0 40 e4 cb 6f 78 c0 90  f8 e6 0d 73 89 fe 0a 98  |[email protected]....|
00000070  04 45 39 0c e6 32 ae 26  c5 13 0e ca fb e6 bc f2  |.E9..2.&........|
00000080  49 57 65 da 79 c1 4f 03  f7 97 ec 8c 72 59 cf ac  |IWe.y.O.....rY..|
00000090  64 d6 fe 87 6e 18 5e 81  2c 9b a3 6a b5 10 12 da  |d...n.^.,..j....|

(4) Use this as random source:

shuf -i1-1000 --random-source=<(./seed-and-counter.sh 320 | xargs -d'\n' -n 1 ./bin-hash-lines.sh) | tail
430
854
890
580
441
960
944
332
687
703

Known issue: The helper scripts and the xargs command seem to keep running.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .