Во-первых, обратите внимание, что $2^{16}$-длинная таблица поиска 16-битных = 2-байтовых записей занимает 131 072 байта пространства.
Ваш вопрос очень зависит от архитектуры. Для быстрого шифрования вы хотели бы, чтобы S-загруженный в самый быстрый бит кэш-памяти (кэш L1 является часто используемым термином). Теперь Pentium III, например, 32 КБ кэш-памяти L1 который мог бы легко справиться с S-box 256B, но не смог бы справиться с вашим S-Box. Это было бы перестановкой разделов таблицы и снижением производительности. Более современные процессоры, такие как серия Xeon, 1-2 МБ кэш-памяти L1 а может и справиться. Если вы хотите зашифровать что-то в средах с ограниченными ресурсами, таких как мобильные телефоны и датчики IoT (и это находится в центре внимания большинства разработок блочных шифров в наши дни), обратите внимание, что, например, Кэш ARM Cortex A L1 обычно составляет 32 КБ или 64 КБ. и не справился бы хорошо.
Общий эффект, вероятно, намного меньше, чем коэффициент 256 (но опять же на это повлияет скорость шины, зависящая от архитектуры). Однако разница во времени, вызванная подкачкой кеша, увеличивает опасность атак по сторонним каналам по времени (Бернштейн «Атаки по времени кэширования на AES» показали, что эффекты синхронизации кэша могут вызывать уязвимости в реализациях AES). Теперь это становится вопросом не только ухудшения производительности, но и ухудшения безопасности.