jm + random   15

Sattolo's algorithm
produces a randomized permutation of a list, with exactly one cycle (which guarantees that we will reach every element of the list even though we’re traversing it in random order)
algorithms  lists  permutation  random  randomization  cycles 
august 2017 by jm
[Cryptography] Bridge hand record generator cracked
'How to cheat at Bridge by breaking the tournament card-dealing random number generator', via Tony Finch
crypto  security  rngs  prngs  random  bridge  cards  via:fanf 
september 2016 by jm
Darts, Dice, and Coins
Earlier this year, I asked a question on Stack Overflow about a data structure for loaded dice. Specifically, I was interested in answering this question: "You are given an n-sided die where side i has probability pi of being rolled. What is the most efficient data structure for simulating rolls of the die?"

This data structure could be used for many purposes. For starters, you could use it to simulate rolls of a fair, six-sided die by assigning probability 1616 to each of the sides of the die, or a to simulate a fair coin by simulating a two-sided die where each side has probability 1212 of coming up. You could also use this data structure to directly simulate the total of two fair six-sided dice being thrown by having an 11-sided die (whose faces were 2, 3, 4, ..., 12), where each side was appropriately weighted with the probability that this total would show if you used two fair dice. However, you could also use this data structure to simulate loaded dice. For example, if you were playing craps with dice that you knew weren't perfectly fair, you might use the data structure to simulate many rolls of the dice to see what the optimal strategy would be. You could also consider simulating an imperfect roulette wheel in the same way.

Outside the domain of game-playing, you could also use this data structure in robotics simulations where sensors have known failure rates. For example, if a range sensor has a 95% chance of giving the right value back, a 4% chance of giving back a value that's too small, and a 1% chance of handing back a value that's too large, you could use this data structure to simulate readings from the sensor by generating a random outcome and simulating the sensor reading in that case.

The answer I received on Stack Overflow impressed me for two reasons. First, the solution pointed me at a powerful technique called the alias method that, under certain reasonable assumptions about the machine model, is capable of simulating rolls of the die in O(1)O(1) time after a simple preprocessing step. Second, and perhaps more surprisingly, this algorithm has been known for decades, but I had not once encountered it! Considering how much processing time is dedicated to simulation, I would have expected this technique to be better- known. A few quick Google searches turned up a wealth of information on the technique, but I couldn't find a single site that compiled together the intuition and explanation behind the technique.


(via Marc Brooker)
via:marcbrooker  algorithms  probability  algorithm  coding  data-structures  alias  dice  random 
april 2016 by jm
Just use /dev/urandom to generate random numbers
Using SHA-1 [to generate random numbers] in this way, with a random seed and a counter, is just building a (perfectly sound) CSPRNG with, I believe, an 80-bit security level. If you trust the source of the random seed, e.g. /dev/urandom, you may as well just use /dev/urandom itself. If you don't, you're already in trouble.

And if you somehow need a userspace PRNG, the usual advice about not rolling your own crypto unless you know what you're doing applies. (Especially for database IDs, the risk of collisions should be considered a security problem, ergo this should be considered crypto, until proven otherwise.) In this case, using BLAKE2 instead of SHA-1 would get you a higher security level and faster hashing.

Or, in tptacek's words: http://sockpuppet.org/blog/2014/02/25/safely-generate-random-numbers/
random  randomness  urandom  uuids  tptacek  hackernews  prng 
november 2015 by jm
A Tour Through Random Ruby
turns out Ruby has a good set of random-text-generation gems on offer
random  ruby  coding  text-generation  markov-chain  gems 
july 2015 by jm
murbul comments on The security issue of Blockchain.info's Android Wallet is not about system's entropy. It's their own BUGs on PRNG again!
I was in the middle of writing a breakdown of what went wrong, but you've beat me to it.
Basically, they have a LinuxSecureRandom class that's supposed to override the standard SecureRandom. This class reads from /dev/urandom and should provide cryptographically secure random values.
They also seed the generator using SecureRandom#setSeed with data pulled from random.org. With their custom SecureRandom, this is safe because it mixes the entropy using XOR, so even if the random.org data is dodgy it won't reduce security. It's just an added bonus.
BUT! On some devices under some circumstances, the LinuxSecureRandom class doesn't get registered. This is likely because /dev/urandom doesn't exist or can't be accessed for some reason. Instead of screaming bloody murder like any sensible implementation would, they just ignore that and fall back to using the standard SecureRandom.
If the above happens, there's a problem because the default implementation of SecureRandom#setSeed doesn't mix. If you set the seed, it replaces the entropy entirely. So now the entropy is coming solely from random.org.
And the final mistake: They were using HTTP instead of HTTPS to make the webservice call to random.org. On Jan 4, random.org started enforcing HTTPS and returning a 301 Permanently Moved error for HTTP - see https://www.random.org/news/. So since that date, the entropy has actually been the error message (turned into bytes) instead of the expected 256-bit number. Using that seed, SecureRandom will generate the private key for address 1Bn9ReEocMG1WEW1qYjuDrdFzEFFDCq43F 100% of the time. Ouch. This is around the time that address first appears, so the timeline matches.
I haven't had a thorough look at what they've replaced it with in the latest version, but initial impressions are that it's not ideal. Not disastrous, but not good.


Always check return values; always check HTTP status codes.
bugs  android  fail  securerandom  random  prng  blockchain.info  bitcoin  http  randomness  entropy  error-checking 
may 2015 by jm
Postcodes at last but random numbers don’t address efficiency
Karlin Lillington assembles a fine collection of quotes from various sources panning the new Eircode system:
Critics say the opportunity has been missed to use Ireland’s clean-slate status to produce a technologically innovative postcode system that would be at the cutting edge globally; similar to the competitive leap that was provided when the State switched to a digital phone network in the 1980s, well ahead of most of the world.
Instead, say organisations such as the Freight Transport Association of Ireland (FTAI), the proposed seven-digit format of scrambled letters and numbers is almost useless for a business sector that should most benefit from a proper postcode system: transport and delivery companies, from international giants like FedEx and UPS down to local courier, delivery and service supplier firms.
Because each postcode will reveal the exact address of a home or business, privacy advocates are concerned that online use of postcodes could link many types of internet activity, including potentially sensitive online searches, to a specific household or business.
eircode  government  fail  ireland  postcodes  location  ftai  random 
september 2014 by jm
OpenSSL Valhalla Rampage
OpenBSD are going wild ripping out "arcane VMS hacks" in an attempt to render OpenSSL's source code comprehensible, and finding amazing horrors like this:

'Well, even if time() isn't random, your RSA private key is probably pretty random. Do not feed RSA private key information to the random subsystem as entropy. It might be fed to a pluggable random subsystem…. What were they thinking?!'
random  security  openssl  openbsd  coding  horror  rsa  private-keys  entropy 
april 2014 by jm
The New York Review of Bots
'Welcome to the New York Review of Bots, a professional journal of automated-agent studies. We aspire to the highest standards of rigorous analysis, but will often just post things we liked that a computer made.'
robots  bots  tumblr  ai  word-frequency  markov-chain  random  twitter 
october 2013 by jm
Randomly Failed! The State of Randomness in Current Java Implementations
This would appear to be the paper which sparked off the drama around BitCoin thefts from wallets generated on Android devices:

The SecureRandom PRNG is the primary source of randomness for Java and is used e.g., by cryptographic operations. This underlines its importance regarding security. Some of fallback solutions of the investigated implementations [are] revealed to be weak and predictable or capable of being influenced. Very alarming are the defects found in Apache Harmony, since it is partly used by Android.


More on the BitCoin drama: https://bitcointalk.org/index.php?topic=271486.40 , http://bitcoin.org/en/alert/2013-08-11-android
android  java  prng  random  security  bugs  apache-harmony  apache  crypto  bitcoin  papers 
august 2013 by jm
incompetent error-handling code in the mongo-java-driver project
an unexplained invocation of Math.random() in the exception handling block of this MongoDB java driver class causes roflscale lols in the github commit notes. http://stackoverflow.com/a/16833798 has more explanation.
github  commits  mongodb  webscale  roflscale  random  daily-wtf  wtf 
may 2013 by jm
Vaccination 'herd immunity' demonstration
'Stochastic monte-carlo epidemic SIR model to reveal herd immunity'. Fantastic demo of this important medical concept (via Colin Whittaker)
via:colinwh  stochastic  herd-immunity  random  sir  epidemics  health  immunity  vaccination  measles  medicine  monte-carlo-simulations  simulations 
april 2013 by jm
Colm argues against the 'sleep rand % 3600' hack
it's not sufficiently evenly-distributed, apparently. Also: got linked from Hack The Planet!
scheduling  probability  sleep  unix  updating  cron  random  from delicious
september 2009 by jm

Copy this bookmark:



description:


tags: