diff --git a/src/random.h b/src/random.h
--- a/src/random.h
+++ b/src/random.h
@@ -136,11 +136,33 @@
     inline uint64_t operator()() { return rand64(); }
 };
 
+/**
+ * More efficient than using std::shuffle on a FastRandomContext.
+ *
+ * This is more efficient as std::shuffle will consume entropy in groups of
+ * 64 bits at the time and throw away most.
+ *
+ * This also works around a bug in libstdc++ std::shuffle that may cause
+ * type::operator=(type&&) to be invoked on itself, which the library's
+ * debug mode detects and panics on. This is a known issue, see
+ * https://stackoverflow.com/questions/22915325/avoiding-self-assignment-in-stdshuffle
+ */
+template <typename I, typename R> void Shuffle(I first, I last, R &&rng) {
+    while (first != last) {
+        size_t j = rng.randrange(last - first);
+        if (j) {
+            using std::swap;
+            swap(*first, *(first + j));
+        }
+        ++first;
+    }
+}
+
 /**
  * Number of random bytes returned by GetOSRand.
- * When changing this constant make sure to change all call sites, and make sure
- * that the underlying OS APIs for all platforms support the number (many cap
- * out at 256 bytes).
+ * When changing this constant make sure to change all call sites, and make
+ * sure that the underlying OS APIs for all platforms support the number.
+ * (many cap out at 256 bytes).
  */
 static const ssize_t NUM_OS_RANDOM_BYTES = 32;
 
diff --git a/src/test/random_tests.cpp b/src/test/random_tests.cpp
--- a/src/test/random_tests.cpp
+++ b/src/test/random_tests.cpp
@@ -79,7 +79,43 @@
         for (int j = 1; j <= 10; ++j) {
             BOOST_CHECK(std::find(test.begin(), test.end(), j) != test.end());
         }
+        Shuffle(test.begin(), test.end(), ctx);
+        for (int j = 1; j <= 10; ++j) {
+            BOOST_CHECK(std::find(test.begin(), test.end(), j) != test.end());
+        }
+    }
+}
+
+/** Test that Shuffle reaches every permutation with equal probability. */
+BOOST_AUTO_TEST_CASE(shuffle_stat_test) {
+    FastRandomContext ctx(true);
+    uint32_t counts[5 * 5 * 5 * 5 * 5] = {0};
+    for (int i = 0; i < 12000; ++i) {
+        int data[5] = {0, 1, 2, 3, 4};
+        Shuffle(std::begin(data), std::end(data), ctx);
+        int pos = data[0] + data[1] * 5 + data[2] * 25 + data[3] * 125 +
+                  data[4] * 625;
+        ++counts[pos];
+    }
+    unsigned int sum = 0;
+    double chi_score = 0.0;
+    for (int i = 0; i < 5 * 5 * 5 * 5 * 5; ++i) {
+        int i1 = i % 5, i2 = (i / 5) % 5, i3 = (i / 25) % 5, i4 = (i / 125) % 5,
+            i5 = i / 625;
+        uint32_t count = counts[i];
+        if (i1 == i2 || i1 == i3 || i1 == i4 || i1 == i5 || i2 == i3 ||
+            i2 == i4 || i2 == i5 || i3 == i4 || i3 == i5 || i4 == i5) {
+            BOOST_CHECK(count == 0);
+        } else {
+            chi_score += ((count - 100.0) * (count - 100.0)) / 100.0;
+            BOOST_CHECK(count > 50);
+            BOOST_CHECK(count < 150);
+            sum += count;
+        }
     }
+    BOOST_CHECK(chi_score > 58.1411); // 99.9999% confidence interval
+    BOOST_CHECK(chi_score < 210.275);
+    BOOST_CHECK_EQUAL(sum, 12000);
 }
 
 BOOST_AUTO_TEST_SUITE_END()
diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp
--- a/src/wallet/coinselection.cpp
+++ b/src/wallet/coinselection.cpp
@@ -256,7 +256,7 @@
     std::vector<OutputGroup> applicable_groups;
     Amount nTotalLower = Amount::zero();
 
-    random_shuffle(groups.begin(), groups.end(), GetRandInt);
+    Shuffle(groups.begin(), groups.end(), FastRandomContext());
 
     for (const OutputGroup &group : groups) {
         if (group.m_value == nTargetValue) {
diff --git a/src/wallet/wallet.cpp b/src/wallet/wallet.cpp
--- a/src/wallet/wallet.cpp
+++ b/src/wallet/wallet.cpp
@@ -2722,7 +2722,7 @@
         // may result in privacy leaks as they will potentially be
         // deterministically sorted. We solve that by explicitly shuffling the
         // outputs before processing
-        std::shuffle(vCoins.begin(), vCoins.end(), FastRandomContext());
+        Shuffle(vCoins.begin(), vCoins.end(), FastRandomContext());
     }
     std::vector<OutputGroup> groups =
         GroupOutputs(vCoins, !coin_control.m_avoid_partial_spends);
@@ -3222,8 +3222,8 @@
         txNew.vin.clear();
         std::vector<CInputCoin> selected_coins(setCoins.begin(),
                                                setCoins.end());
-        std::shuffle(selected_coins.begin(), selected_coins.end(),
-                     FastRandomContext());
+        Shuffle(selected_coins.begin(), selected_coins.end(),
+                FastRandomContext());
 
         // Note how the sequence number is set to non-maxint so that
         // the nLockTime set above actually works.