Las cajas S criptográficas son funciones booleanas vectoriales que deben cumplir criterios estrictos para proporcionar seguridad a los algoritmos criptográficos. Hay varios métodos existentes para generar cajas S criptográficas fuertes, incluidos algoritmos de búsqueda estocástica. Estos algoritmos de búsqueda suelen generar funciones booleanas candidatas aleatorias (o permutaciones) que se mejoran durante la búsqueda examinando el espacio de búsqueda de una manera específica. Aquí, presentamos un nuevo tipo de algoritmo estocástico para generar cajas S criptográficas. No generamos y luego mejoramos la función booleana; en su lugar, construimos el vector de valores incrementalmente. Los nuevos valores se obtienen mediante una búsqueda aleatoria impulsada por restricciones en el espectro diferencial de la caja S generada. En este artículo, formulamos dos nuevos algoritmos basados en este nuevo enfoque y estudiamos el mejor en mayor detalle. Demostramos la corrección del algoritmo propuesto y evaluamos su complejidad. La parte final contiene una evaluación experimental del método. Mostramos que el algoritmo genera cajas S con mejores propiedades que una búsqueda aleatoria. Creemos que nuestro enfoque puede ser ampliado en el futuro adoptando métodos de búsqueda estocástica más avanzados.