Ask Ben: Fisher-Yates Shuffle Algorithm In ColdFusion

I have been using code you shared on the internet to generate random passwords for a club site for years. Now my ISP all of the sudden changed the ColdFusion security to deny java.util.Collections. Is there an easy work around I am missing?

Often times, when I have to randomly shuffle an array in ColdFusion, I'll use Java's Collections.shuffle() method. But, this requires access to the Java objects on the server, which not all servers allow. As such, we might need to reproduce the shuffle() functionality in our CFML code.

Under the hood, the Collections class uses the Fisher-Yates shuffle algorithm (or at least it did the last time I checked). This is a relatively straightforward algorithm that loops over an array and randomly swaps the current element with another element farther down in the array (ie, with another element that has not yet been visited).

To implement this algorithm, we're going to lean on two native functions in ColdFusion:

• randRange( m, n [, algorithm] ) - we'll use this function randomly select which indices to swap within the array. And, we'll default to using the sha1prng pseudo-random number generator algorithm for a more "secure" randomization.

• arraySwap( array, i, j ) - once we've chosen our indices to swap, we'll use this function perform the swap. No intermediary, temporary variables required.

To demonstrate, I'm going to create an array of digits (0..9) so that it's easy to see how much shuffling has been applied to the array:

<cfscript>

	letters = listToArray( "0123456789", "" );

	outputArray( shuffleArray( duplicate( letters ) ) );
	outputArray( shuffleArray( duplicate( letters ) ) );
	outputArray( shuffleArray( duplicate( letters ) ) );
	outputArray( shuffleArray( duplicate( letters ) ) );
	outputArray( shuffleArray( duplicate( letters ) ) );

	// ------------------------------------------------------------------------------- //
	// ------------------------------------------------------------------------------- //

	/**
	* Implementation of the Fisher-Yates shuffle algorithm using randRange() internally.
	* This algorithm is designed to perform an in-place mutation of the array (assuming
	* that you have enabled the "passArrayByReference" application setting).
	*/
	public array function shuffleArray(
		required array values,
		string algorithm = "sha1prng"
		) {

		var length = arrayLen( values );

		for ( var i = 1 ; i < length ; i++ ) {

			arraySwap( values, i, randRange( i, length, algorithm ) );

		}

		return( values );

	}


	/**
	* I serialize the given values array to the screen followed by a BR-tag.
	*/
	public void function outputArray( required array values ) {

		writeOutput( values.toList( "," ) & "<br />" );

	}

</cfscript>

As you can see, the algorithm uses a simple for-loop to iterate over 1..n-1. For each index, i, we randomly swap it with another index in the range, i..n. And, when we run this ColdFusion code, we get the following output:

4,1,5,6,0,8,7,2,3,9
6,0,1,8,7,5,4,2,9,3
2,5,8,7,6,1,0,4,3,9
7,1,0,9,4,2,8,3,5,6
1,7,6,3,0,9,4,2,8,5

Much shuffled! Such random!

By design, the Fisher-Yates algorithm performs an in-place mutation of the array. However, the mutation is only in-place if you've configured your ColdFusion runtime to pass arrays by reference (this is the default behavior in Lucee CFML but not in Adobe ColdFusion). In my version, I make sure to return the shuffled array in case your runtime is configured to pass arrays by value.

Generating Random Passwords Without Shuffling

The original question mentioned that the .shuffle() method was being used to generate a random password. So, I thought it would be worth a quick exploration of password generation. We don't actually need to shuffle anything for password generation—we can use the randRange() function to randomly select from a set of valid inputs.

In the following demo, I'm defining a string that contains all the valid input characters (letters, numbers, and special characters). Then, I'm using the randRange() function with the sha1prng algorithm to securely and randomly pick N-characters:

<cfscript>

	// These are all the possible characters that can be used in the password.
	inputs = (
		"0123456789" &
		"abcdefghijklmnopqrstuvwxyz" &
		"ABCDEFGHIJKLMNOPQRSTUVWXYZ" &
		"~!@##$%^&*_+=-[]()<>.,?/\|"
	);

	letters = listToArray( inputs, "" );

	// Generate random passwords.
	outputPassword( generatePassword( 20, letters ) );
	outputPassword( generatePassword( 20, letters ) );
	outputPassword( generatePassword( 20, letters ) );
	outputPassword( generatePassword( 20, letters ) );
	outputPassword( generatePassword( 20, letters ) );

	// ------------------------------------------------------------------------------- //
	// ------------------------------------------------------------------------------- //

	/**
	* I generate a random password of the given length, choosing from the given alphabet.
	*/
	public string function generatePassword(
		required numeric length,
		required array alphabet
		) {

		var alphabetLength = arrayLen( alphabet );
		var chosenLetters = [];

		for ( var i = 1 ; i <= length ; i++ ) {

			// By using the SHA1PRNG algorithm, we are "securely" selecting letters
			// randomly from the given alphabet.
			chosenLetters[ i ] = alphabet[ randRange( 1, alphabetLength, "sha1prng" ) ];

		}

		return arrayToList( chosenLetters, "" );

	}


	/**
	* I output the given password, encoding for HTML so that "<" characters don't break
	* the page rendering.
	*/
	public void function outputPassword( required string value ) {

		writeOutput( encodeForHtml( value ) & "<br />" );

	}

</cfscript>

As you can see, there's no shuffling involved. The randomization comes from the selection of the input characters, not from the reorganization of the selected characters. And, when we run this ColdFusion code, we get the following output:

LOM3u#rkY(x%RfUSI,.L
9#0X/\ts5T5tpp-DfSaF
=D<R27QkP/~18K^R|6h)
=NP_A.3w-b5^0iAYBXHI
X?Gq$EeJnj4&4G*b\5%.

The only requirement this password algorithm satisfies is one of length. Meaning, there's no guarantee of any given subset of letters. In other words, this algorithm doesn't ensure mandates like "One uppercase, one lowercase, and one special character". But, in recent years, this type of mandate has fallen out of favor with NIST (the National Institute of Standards and Technology). Today, NIST's password policy favors length over all other constraints. Which is good for us because it makes our algorithms easier to code!

As much as I like the idea of shuffling arrays, I've come to favor using randRange() (with the sha1prng algorithm) in most cases. In fact, this is the technique that I now use for generating all of my cryptographically secure tokens.

Want to use code from this post? Check out the license.

Short link: https://bennadel.com/4606