ciphey Documentation

The A* search algorithm in ciphey is used to find the optimal sequence of decoders to decode encrypted or encoded text. Recent improvements have made the search more focused and efficient by implementing decoder-specific nodes and a multi-component heuristic function.

Key Implemented Features:

• Decoder-Specific Nodes: Instead of trying all decoders for every state, the algorithm can create nodes that target a specific next_decoder_name. This reduces the search space by filtering available decoders to only the one specified in the node.
• Simplified Heuristic Function: The heuristic guides the search using three components:
  1. Popularity Component: Prioritizes decoders based on their usage frequency.
  2. Depth Penalty: Uses an exponential penalty (0.05 * path.len() as f32).powi(2) to discourage excessively deep decoding paths.
  3. Uncommon Sequence Penalty: Adds a fixed penalty (0.25) for decoder sequences that are statistically uncommon.
• Adaptive Depth Penalty & String Quality: The algorithm now incorporates string quality and adaptive penalties to prevent unproductive paths.

To prevent multiple threads from prompting the user simultaneously, the human_checker function in src/checkers/human_checker.rs uses a global mutex named HUMAN_CHECKER_MUTEX. When a thread calls human_checker, it must acquire this lock before proceeding with the check. Other threads attempting to run the human checker will block until the current thread releases the lock.

Note that if config.human_checker_on is false or config.api_mode is enabled, the function returns true immediately without attempting to acquire the lock or prompt the user.

// Global mutex to ensure only one thread runs the human checker at a time
static HUMAN_CHECKER_MUTEX: Lazy<Mutex<()>> = Lazy::new(|| Mutex::new(()));

pub fn human_checker(input: &CheckResult) -> bool {
    // ... (config checks) ...
    
    // Acquire the mutex to ensure only one thread runs the human checker at a time
    let _guard = HUMAN_CHECKER_MUTEX.lock().unwrap();
    
    human_checker_check(&input.description, &input.text);
    // ... (prompting logic) ...
}

The A* search algorithm in ciphey (src/searchers/astar.rs) utilizes the parallelized decoder system but maintains a sequential structure for node processing to ensure optimality.

Execution Model

1. Sequential Node Processing: Nodes are pulled from the priority queue one at a time based on their f-score (f = g + h). This creates a sequential bottleneck because nodes must be processed in a specific order.
2. Parallel Decoder Execution: While node processing is sequential, the actual decoding work performed on each node is parallelized across multiple threads.

Potential Optimization Areas

Beyond decoder execution, performance in the A* implementation could be improved through:

• Parallel Pruning: Parallelizing quality scoring and sorting during pruning operations.
• Parallel Heuristics: Calculating heuristic values for multiple nodes simultaneously.
• Load Balancing: Improving how workloads are distributed across threads to prevent idle cores.

The Athena checker (src/checkers/athena.rs) acts as the main orchestrator for the plaintext identification system. It coordinates multiple specialized sub-checkers to determine if a string is valid plaintext.

When a check is requested, it follows this priority logic:

1. Regex Check: If a regex pattern is provided in the configuration, it uses the RegexChecker. If a match is found, it may optionally verify the result with the Human checker.
2. Structured Data Check: If no regex is provided (or no match is found), it first attempts to identify the text using the LemmeKnow checker.
3. Natural Language Check: If LemmeKnow does not identify the text, it attempts to identify it using the English checker.

For both LemmeKnow and English checkers, if they identify the text as plaintext, the result can optionally be verified by the Human checker. The Athena checker returns as soon as any sub-checker identifies the text as plaintext.

While parallelizing decoder execution improves performance by utilizing multiple CPU cores, developers and users should be aware of the following performance constraints:

Saturation Points

Adding more parallelism does not always result in linear speedup due to:

• CPU Core Utilization: Once all cores are fully utilized by decoder execution, adding more layers of parallelism (e.g., parallelizing search nodes) may yield diminishing returns.
• Overhead: Thread management, synchronization, and context switching introduce overhead that can degrade performance if the tasks are too small.
• Memory Bandwidth: Multiple threads competing for memory access can create contention, making memory bandwidth the bottleneck instead of CPU power.

Amdahl's Law

The theoretical speedup is limited by the sequential portions of the algorithm. The formula used is:

Speedup = 1 / ((1 - P) + P/N)

Where:

• P is the proportion of the program that can be parallelized.
• N is the number of processors.

The HashCrackDecoder is designed to reverse cryptographic hashes (such as MD5, SHA1, and SHA256) using two primary methods: Wordlist Lookup and Rainbow Table methods.

Wordlist Lookup Method

1. Detect Hash Type: Identifies the algorithm used by the input hash.
2. Cache Check: Checks if the appropriate wordlist is available locally.
3. Download: If not cached, downloads the wordlist from S3.
4. Search: Searches the wordlist (formatted as hash:plaintext) for the input hash.
5. Result: Returns the cracked plaintext if a match is found.

Rainbow Table Method

1. Detect Hash Type: Identifies the algorithm.
2. Size Selection: Attempts to use rainbow tables in increasing order of size: 10GB, 50GB, then 100GB.
3. Cache/Download: Checks local cache or downloads the table from S3.
4. Search: Uses a time-memory tradeoff (applying reduction functions and checking endpoints) to find the cracked value.