Критерии выбора S box в древнем DES были раскрыты только в 1994 году, и только после этого стало что-то понятно. Например, что АНБ метод дифференциального криптоанализа был известен ещё тогда.

Я бы не стал доверять алгоритму с S box при наличии альтернатив. Может, он выбирался из соображений стойкости, может, для бэкдора - des Sbox не анализировал только ленивый, но до той публикации 94 года без особых успехов. Про полный рандом это точно левая отмазка, уж авторы криптоалгоритмов в курсе как минимум про rfc4076:)