Investigation Methodology
Task-List
Broadcast Attack Decision Tree
├── 🔢 Multiple Moduli + Same Exponent?
│ ├── ✅ YES → Use CRT (Hastad's Attack)
│ └── ❌ NO → Continue analysis
├── 🔗 Known Message Relationships?
│ ├── ✅ Linear → Franklin-Reiter Attack
│ ├── ✅ Polynomial → Coppersmith's Method
│ ├── ✅ Known Differences → Algebraic Solving
│ └── ❌ NO → Continue analysis
├── 🎯 Structured Messages?
│ ├── ✅ YES → Stereotyped Message Attack
│ └── ❌ NO → Continue analysis
├── 📐 Same Modulus?
│ ├── ✅ YES → Direct Algebraic Methods
│ └── ❌ NO → Advanced Lattice TechniquesDetection Methods
Check for small exponent
if e < 65537:
print("WARNING: Small public exponent detected!"Check for no padding
if message_size == modulus_size:
print("WARNING: No padding detected!")Check for multiple encryptions
if same_message_encrypted_multiple_times:
print("WARNING: Broadcast attack possible!")Check for potential Wiener's vulnerability
if e > n**0.5:
suggestions.append("Wiener's Attack (small d suspected)")Check for Fermat's vulnerability
sqrt_n = int(n**0.5)
if (sqrt_n + 1)**2 - n < sqrt_n:
suggestions.append("Fermat's Factorization (close primes)"Check modulus size for general factorization
bit_length = n.bit_length()
if bit_length < 1024:
suggestions.append("General Factorization (weak key size)")Check for common modulus
if additional_info and 'shared_modulus' in additional_info:
suggestions.append("Common Modulus Attack")POC
def analyze_rsa_parameters(e, n, additional_info=None):
"""
Analyze RSA parameters to suggest appropriate attacks
"""
suggestions = []
# Check for small exponent
if e < 65537:
suggestions.append("Small Exponent Attack")
# Check for potential Wiener's vulnerability
if e > n**0.5:
suggestions.append("Wiener's Attack (small d suspected)")
# Check for Fermat's vulnerability
sqrt_n = int(n**0.5)
if (sqrt_n + 1)**2 - n < sqrt_n:
suggestions.append("Fermat's Factorization (close primes)")
# Check modulus size for general factorization
bit_length = n.bit_length()
if bit_length < 1024:
suggestions.append("General Factorization (weak key size)")
# Check for common modulus
if additional_info and 'shared_modulus' in additional_info:
suggestions.append("Common Modulus Attack")
return suggestionsSmall Parameter Attacks
Elliptic Curve Cryptography
POC
def small_parameter_ec_attack(curve_order, private_key_bits):
"""
Attack weak elliptic curves with small parameters
"""
if curve_order.bit_length() < 256:
return "Vulnerable to brute force"
if private_key_bits < 128:
return "Weak private key - brute force possible"Discrete Logarithm Systems
POC
def small_subgroup_attack(g, p, q):
"""
Attack discrete log when subgroup order is small
"""
if q < 2**80: # Small subgroup
return "Vulnerable to Pollard's Rho on small subgroup"Lattice-Based Cryptography
def lattice_small_secret_attack(lattice_basis, error_bound):
"""
Attack lattice systems with small secrets/errors
Similar principle to small exponent attacks
"""
if error_bound < lattice_dimension_threshold:
return "Vulnerable to lattice reduction attacks"Broadcast Attacks
Linear Relationship Attack
POC
def linear_broadcast_attack(c1, c2, n, e, a, b, c, d):
"""
Attack when messages have linear relationship:
m₁ = a*m + b
m₂ = c*m + d
Where m is the target message
"""
# Given:
# c₁ ≡ (a*m + b)^e (mod n)
# c₂ ≡ (c*m + d)^e (mod n)
# For small e (like e=3), we can expand and solve
if e == 3:
# Expand (a*m + b)³ and (c*m + d)³
# Create system of equations in powers of m
# Solve algebraically
# This is complex algebra - conceptual example
print("Solving linear system for e=3 case")
# Extract coefficients and solve polynomial system
# Returns the original message m
pass
return None
# Example usage:
# If we know m₁ = 2m + 5 and m₂ = 3m + 7
# We can solve even without CRTKnown Difference Attack
POC
def known_difference_attack(c1, c2, n, e, diff):
"""
Attack when messages differ by a known amount:
m₂ = m₁ + diff
"""
# Given:
# c₁ ≡ m₁^e (mod n)
# c₂ ≡ (m₁ + diff)^e (mod n)
# For small e, expand (m₁ + diff)^e using binomial theorem
# Create equation involving only m₁
if e == 3:
# c₂ ≡ m₁³ + 3*m₁²*diff + 3*m₁*diff² + diff³ (mod n)
# Rearrange: c₂ - diff³ ≡ m₁³ + 3*m₁²*diff + 3*m₁*diff² (mod n)
# Factor: c₂ - diff³ ≡ m₁(m₁² + 3*m₁*diff + 3*diff²) (mod n)
# This creates a relationship we can exploit
modified_c2 = (c2 - pow(diff, 3, n)) % n
# Now we have a relationship between c1 and modified_c2
# Can solve using various techniques
pass
return NoneFranklin-Reiter Related Message Attack
POC
def franklin_reiter_attack(c1, c2, n, e, a, b):
"""
Franklin-Reiter attack for related messages
m₁ and m₂ where m₂ ≡ a*m₁ + b (mod n)
This DOES NOT use CRT!
Uses resultants and polynomial GCD
"""
from sympy import symbols, Poly, resultant
if e < 2:
return None
x = symbols('x')
# Define polynomials
# f₁(x) = x^e - c₁
# f₂(x) = (a*x + b)^e - c₂
f1 = Poly(x**e - c1, x)
f2 = Poly((a*x + b)**e - c2, x)
# Compute resultant to eliminate x
# If m₁ is a common root, resultant will be 0
# This gives us information about m₁
res = resultant(f1, f2, x)
# The resultant gives us a way to find m₁
# without using CRT - pure polynomial algebra
# Solve for roots of the resultant
# (Implementation details depend on specific case)
print("Franklin-Reiter uses polynomial resultants, not CRT")
return NoneStereotyped Message Attack
POC
def stereotyped_message_attack(ciphertexts, n, e, known_parts, unknown_part_size):
"""
Attack messages with known structure:
"Dear Alice, [SECRET], Best regards, Bob"
Uses Coppersmith's method, not CRT
"""
# Messages have form: known_prefix + unknown + known_suffix
# Use Coppersmith's technique to find small unknown parts
# This works even with a single ciphertext!
# No need for multiple encryptions or CRT
# Set up polynomial with unknown part as variable
# Use lattice reduction to find small roots
print("Stereotyped messages use Coppersmith's method")
print("No CRT required - works on single ciphertext")
return NoneLast updated