Challenge: HAWK_II
Category: Cryptography
Difficulty: Medium
Flag: 0xfun{tOO_LLL_256_B_kkkkKZ_t4e_f14g_F14g}

Challenge Overview

HAWK_II is a cryptography challenge based on the HAWK (HAWK: Module LIP Makes Lattice Signatures Fast, Compact and Simple) post-quantum signature scheme. The challenge provides us with:

1. Implementation files:

• hawk.sage - Full HAWK signature scheme implementation in SageMath
• Hawk_II.sage - Challenge script that generates keys and encrypts the flag

1. Output data:

• Encrypted flag (AES-256-CBC)
• Public key components
• Secret key (LEAKED!)
• Partial coefficient leakage data

Understanding the HAWK Signature Scheme

HAWK is a lattice-based signature scheme that operates over cyclotomic fields. The key components are:

Key Structure

sk = (f, g, F, G)  # Secret key - 4 polynomials in cyclotomic field
pk = (q00, q10, q11)  # Public key - Hermitian form components

Where:

• f, g - Small polynomials sampled from discrete Gaussian
• F, G - Computed via NTRU equation: fG - gF = 1
• The secret key forms a basis for a lattice

Cyclotomic Fields

The scheme works over Q(ζ_{2n}) where n = 256, meaning polynomials of degree 256 with a primitive 512-th root of unity.

Analyzing the Challenge Code

Let’s examine the key generation and encryption process:

# From Hawk_II.sage
n = 256
sigma_kg  = 2
sigma_sig = sqrt(2)
sigma_ver = 2*2

Sig = SignatureScheme(n, sigma_kg, sigma_sig, sigma_ver)
sk, pk = Sig.KGen()# AES encryption of the flag
key = sha256(str(sk).encode()).digest()
iv = urandom(16)
cipher = AES.new(key=key, mode=AES.MODE_CBC, iv=iv)
enc = cipher.encrypt(pad(FLAG, 16))

The Vulnerability

The critical vulnerability is in the output generation:

print("sk = ", sk)  # 🚨 FULL SECRET KEY LEAKED!

The challenge prints the entire secret key to the output file! This makes the challenge trivial — we don’t need to exploit any cryptographic weakness or use lattice reduction techniques. We simply need to:

1. Extract the secret key from the output
2. Compute SHA256(str(sk)) to get the AES key
3. Decrypt the flag

What the Leak Data Was For

The challenge also provides partial coefficient leakage:

leak_data = {
    'indices0': [list of indices],
    'indices1': [list of indices],  
    'leak_vec0': z^254 + 4*z^253 - ...,  # Half of f's coefficients
    'leak_vec1': 2*z^255 + z^252 + ...    # Half of g's coefficients
}

This was likely intended for a more advanced attack using lattice reduction (LLL/BKZ) to recover the full secret key from partial information. However, since the full sk is leaked, this data becomes unnecessary.

Solution

Step 1: Extract the Secret Key

From output.txt, we find the complete secret key printed:

sk = (z^255 + z^254 + 4*z^253 - z^252 - ..., 
      2*z^255 - z^254 + z^253 + z^252 - ...,
      13*z^255 - 17*z^254 - 3*z^253 - ...,
      -z^255 + 5*z^254 - 4*z^253 - ...)

This is the tuple (f, g, F, G) representing the four polynomials in the cyclotomic field.

Step 2: Compute the AES Key

The AES key is derived by hashing the string representation of the secret key:

from hashlib import sha256

sk_str = """(z^255 + z^254 + 4*z^253 - z^252 - z^251 + 2*z^250 + ..., 
             2*z^255 - z^254 + z^253 + z^252 - 4*z^250 + ...,
             13*z^255 - 17*z^254 - 3*z^253 - 8*z^252 + ...,
             -z^255 + 5*z^254 - 4*z^253 - 5*z^252 + ...)"""key = sha256(sk_str.encode()).digest()

Computed Key (hex): 64660d4648893cf4bed757d12e5ed09de3635f107fa419c1fe414eebed53b102

Step 3: Decrypt the Flag

With the key and IV, we can decrypt using AES-256-CBC:

from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad

iv = bytes.fromhex("ac518ee77848d87912548668d3240aa4")
enc = bytes.fromhex("ab425b6c2c0a6760a5e9c52ba25dfc47da97afeeceb9823e553dcccc971b0f25c876ea63ed867d77e3295082064a3f69")cipher = AES.new(key=key, mode=AES.MODE_CBC, iv=iv)
flag = unpad(cipher.decrypt(enc), 16)print(flag.decode())

Complete Solver Script

#!/usr/bin/env python3
from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad

# Given encrypted data
iv_hex = "ac518ee77848d87912548668d3240aa4"
enc_hex = "ab425b6c2c0a6760a5e9c52ba25dfc47da97afeeceb9823e553dcccc971b0f25c876ea63ed867d77e3295082064a3f69"iv = bytes.fromhex(iv_hex)
enc = bytes.fromhex(enc_hex)# The secret key from output.txt (full polynomial strings)
sk_str = """(z^255 + z^254 + 4*z^253 - z^252 - z^251 + 2*z^250 + 3*z^249 + 3*z^246 + z^244 + z^243 - 3*z^242 - 2*z^240 - z^238 - z^237 + 2*z^236 + 2*z^235 - z^234 + 2*z^233 + 3*z^232 - 2*z^231 - z^230 + 2*z^229 - z^228 - 3*z^227 + z^226 - z^224 + 3*z^223 + z^222 + z^221 - 2*z^220 + z^219 - 3*z^218 + 2*z^217 - z^216 + 3*z^215 + 6*z^214 + z^213 - 2*z^212 - 2*z^211 - 3*z^210 - 2*z^209 - z^208 - 3*z^207 - z^206 + z^205 + z^204 + 3*z^203 - z^202 + 3*z^201 + z^200 - 2*z^199 - 5*z^198 - 2*z^197 - 2*z^196 - 2*z^195 + 3*z^194 + 6*z^193 - 2*z^192 + z^191 - 2*z^190 - z^189 + z^187 + 2*z^186 - 3*z^185 - 5*z^184 + 5*z^182 - z^181 + 2*z^180 - 4*z^179 + 3*z^178 - z^177 + z^175 - 4*z^173 - 2*z^171 + z^169 + 2*z^168 + z^167 - z^166 + 4*z^165 - 3*z^164 - 3*z^163 - 3*z^162 + z^161 - 3*z^160 - 3*z^159 + 2*z^158 - 2*z^156 - 2*z^155 + 3*z^154 - z^153 - 2*z^152 - z^151 - 2*z^150 - z^149 + z^148 + z^147 - 4*z^146 - 2*z^145 + 3*z^144 + 4*z^143 - z^142 - 2*z^141 + 2*z^139 - 2*z^138 - 3*z^136 + z^135 + z^134 + 3*z^133 - z^132 + z^131 - 4*z^130 - 2*z^129 - z^128 + z^127 - z^126 - 3*z^125 + z^124 + 2*z^123 + 3*z^122 - 4*z^120 + 6*z^119 - 3*z^118 + z^117 + z^116 + 4*z^115 + 2*z^114 - z^113 + 2*z^112 - z^111 - z^110 - 4*z^109 - 3*z^107 + z^106 + 3*z^105 + 2*z^103 - z^102 + z^101 - z^100 + z^98 + z^95 - 3*z^94 + z^93 - 2*z^92 + z^91 - 5*z^90 + 3*z^89 - z^88 - z^87 - 4*z^86 + z^85 - z^84 + 2*z^82 - 2*z^81 + z^78 + z^75 + 5*z^74 + z^73 + z^71 - 3*z^70 - z^68 + 2*z^67 - z^66 + z^65 - 2*z^64 + 2*z^63 + z^62 - 3*z^61 - 2*z^60 - 3*z^58 + 2*z^57 + z^56 - 2*z^55 + z^54 + z^53 + 4*z^52 - z^51 + z^50 - z^49 + z^48 + z^47 - z^46 + 2*z^45 - z^43 - z^42 + z^41 - z^40 - 7*z^39 + 3*z^38 + 3*z^37 + z^36 - z^35 + 2*z^34 + 2*z^31 + 2*z^29 - 3*z^28 - z^26 + z^25 - z^24 + 2*z^23 - 3*z^22 - z^21 + z^20 - 2*z^18 + z^17 + z^15 - z^14 + 2*z^12 - 2*z^11 - z^10 + 2*z^9 + z^8 - z^7 + z^6 - 3*z^5 - z^4 + 3*z^3 - 5*z^2 - z, 2*z^255 - z^254 + z^253 + z^252 - 4*z^250 + 2*z^249 - z^248 + z^246 + z^244 + 2*z^242 - z^241 + 2*z^239 + 2*z^238 - 2*z^237 - 3*z^236 + z^235 - 2*z^234 + z^233 + 3*z^231 + z^230 + z^229 + 3*z^228 - 2*z^227 - z^226 - z^224 - z^223 + 4*z^222 - 3*z^220 - z^219 + 2*z^218 - z^217 - 2*z^216 + 3*z^215 + 2*z^214 - 2*z^213 + z^210 + z^209 + 5*z^207 + z^206 - z^205 - z^202 - 2*z^200 - 2*z^199 + z^198 + z^197 - z^196 + 3*z^195 + 4*z^194 - 2*z^193 + 3*z^191 - z^189 + 5*z^188 - 5*z^187 + z^185 + 3*z^184 - 4*z^183 + 3*z^182 - z^181 - z^180 + 4*z^179 + 3*z^178 - 3*z^176 + z^175 - z^174 + z^173 - 3*z^171 + z^169 - z^168 - 3*z^167 - z^165 + z^164 + 2*z^162 - z^161 - 2*z^160 + z^158 + 2*z^156 + z^155 + 2*z^154 - z^153 + 4*z^152 - 4*z^151 - 3*z^150 + 4*z^149 - 2*z^147 + z^146 - z^145 - z^144 + z^143 + z^142 - 2*z^140 + 2*z^139 + 2*z^138 + 3*z^137 - 2*z^136 + z^135 - 3*z^134 - 3*z^133 - z^132 + z^131 + 2*z^130 - z^129 + 4*z^128 - z^127 - z^126 + z^125 - 3*z^124 - z^123 + z^122 + z^121 - 3*z^120 + z^119 + z^118 + 3*z^117 - 2*z^116 - z^115 + z^114 + 2*z^113 + 4*z^112 + 2*z^111 - 2*z^110 + z^109 - 2*z^108 + z^107 - 2*z^105 + 4*z^103 - z^101 - 2*z^100 + 6*z^98 + 3*z^97 - z^94 - 2*z^92 - z^91 - 3*z^90 + z^89 + z^88 + 2*z^87 + z^86 - z^85 + 2*z^84 + 2*z^83 - z^82 - 3*z^81 + 3*z^80 - 2*z^79 - 2*z^78 + 2*z^77 + 3*z^76 + z^75 + z^70 - z^69 - z^68 + 2*z^67 - 2*z^66 - z^65 - 3*z^64 - z^63 - 2*z^62 + z^61 + 2*z^60 + 3*z^59 + z^58 + z^57 - 5*z^56 + 2*z^55 + 3*z^54 + z^53 + 4*z^52 + z^51 - z^50 - z^49 + z^48 - 3*z^47 - z^46 + 2*z^44 - z^42 - 3*z^41 + 3*z^38 + z^37 - 2*z^35 - 2*z^34 - z^33 + z^32 + 4*z^31 + 2*z^30 - 2*z^29 - 2*z^27 + z^25 - z^24 - 3*z^23 + 2*z^21 + 2*z^17 - z^16 - 3*z^15 + 2*z^14 + z^12 + 2*z^11 + 2*z^10 + 3*z^9 + 4*z^8 - 2*z^6 - z^5 + 3*z^4 + z^2 + z - 2, 13*z^255 - 17*z^254 - 3*z^253 - 8*z^252 + 7*z^251 - 15*z^250 + 21*z^249 + 11*z^248 - 7*z^247 + 22*z^246 + 3*z^245 - 10*z^244 - 8*z^243 - 12*z^242 + 5*z^241 + 8*z^240 + 4*z^239 - 6*z^238 + 16*z^237 - 2*z^236 + 21*z^235 - z^234 - 14*z^233 - z^232 + 11*z^231 - 5*z^230 + 3*z^229 + 12*z^228 + 11*z^227 + 5*z^226 + 2*z^225 + 18*z^224 - 13*z^222 + 14*z^221 + 6*z^220 - 3*z^219 + 13*z^218 + 2*z^217 - 11*z^216 - 3*z^215 + 8*z^214 + z^213 - 3*z^212 - 11*z^211 - 4*z^210 + 2*z^209 - 16*z^208 + 11*z^207 + 5*z^206 - 12*z^205 + 17*z^204 + 15*z^203 - 5*z^201 - 19*z^200 - 8*z^199 - 11*z^198 + 13*z^197 - 18*z^196 + 18*z^195 - 6*z^194 + z^193 + 6*z^192 - 11*z^191 + 2*z^190 + 7*z^189 - 4*z^188 + 2*z^187 - z^186 + 5*z^185 - 13*z^184 - 6*z^183 - 4*z^182 + 19*z^181 - 4*z^180 + 20*z^179 - 11*z^178 + 5*z^177 - 5*z^176 - z^175 + z^174 + 2*z^172 + 4*z^171 + 3*z^170 + 3*z^169 - 7*z^168 - 9*z^167 - 14*z^166 + 13*z^165 + 2*z^164 - 4*z^163 - 3*z^162 + 7*z^161 + 17*z^160 + 8*z^159 + 6*z^158 - 16*z^157 + 11*z^156 + 17*z^155 + 2*z^154 - 4*z^153 - 5*z^152 + 5*z^151 - 4*z^150 - 2*z^149 + 3*z^148 - 3*z^147 - 7*z^146 + 12*z^145 + 5*z^144 + 5*z^143 - 11*z^142 - 5*z^141 - 9*z^140 - 3*z^139 + 11*z^137 - 7*z^136 + 14*z^135 + 5*z^134 + 12*z^133 - z^132 - z^131 - 14*z^130 - 3*z^129 - 8*z^128 + 7*z^127 + 11*z^126 + 12*z^125 - 2*z^124 + 6*z^123 - 6*z^122 - 2*z^121 - 20*z^120 - 6*z^119 + 2*z^118 + 11*z^117 - 4*z^116 - 9*z^115 - 5*z^114 + 3*z^113 + 5*z^112 + 4*z^111 + 6*z^109 - 8*z^108 + 12*z^107 - z^106 + 6*z^105 + z^104 - 11*z^103 - 9*z^102 - 5*z^101 + 4*z^100 + 5*z^99 + z^98 - 6*z^97 - 9*z^96 + 6*z^95 + 3*z^94 + 10*z^93 - 5*z^92 - 12*z^91 + 4*z^90 - 10*z^89 + 9*z^88 + z^87 + 3*z^86 + z^85 + 17*z^84 + 4*z^83 - 25*z^82 - 4*z^81 - 3*z^80 + 23*z^79 - 6*z^78 - 4*z^77 - 5*z^76 + 7*z^75 + 2*z^74 + 7*z^73 + z^71 - 12*z^70 + 6*z^69 + 7*z^68 - 9*z^67 - 16*z^66 + 16*z^65 - 10*z^64 + 11*z^63 - 6*z^62 + 5*z^61 - 8*z^60 - 3*z^58 + z^57 - 5*z^56 + 11*z^54 - 4*z^53 + 4*z^52 + 7*z^51 - 17*z^50 - 11*z^49 + 14*z^48 + 4*z^47 + 8*z^46 - 7*z^45 - 5*z^44 + 5*z^43 + 9*z^42 - 2*z^41 + 6*z^40 - 9*z^39 - 23*z^38 - 7*z^37 - 10*z^36 + 10*z^35 - z^34 + z^33 - z^32 + 12*z^31 + 9*z^30 - 5*z^29 - z^28 - 18*z^27 + 2*z^26 - 2*z^25 - 6*z^24 + 11*z^23 - 5*z^22 + 5*z^21 + 4*z^20 + 3*z^19 - 2*z^18 - 5*z^17 - 8*z^16 + 8*z^15 + 14*z^14 + 5*z^12 - 12*z^11 - 27*z^10 + 20*z^9 + 10*z^8 - 12*z^7 - 3*z^6 + 8*z^5 - 7*z^4 + 12*z^3 + 4*z^2 - 20*z - 10, -z^255 + 5*z^254 - 4*z^253 - 5*z^252 + 4*z^251 + 3*z^249 - 13*z^248 - 16*z^247 - 7*z^246 + 3*z^245 + 2*z^244 + 3*z^243 + 10*z^242 + 7*z^241 - 15*z^240 - 11*z^239 - 7*z^238 - 5*z^237 + 3*z^236 + 10*z^235 + 3*z^234 - 16*z^233 + 3*z^232 - 13*z^230 + 10*z^229 + 9*z^228 + 14*z^227 - 4*z^226 + 9*z^225 - 18*z^224 - 23*z^223 + 4*z^222 - z^221 + 3*z^219 + 17*z^218 - 9*z^217 + 2*z^216 + 10*z^215 - 17*z^214 - 14*z^213 + 15*z^212 + 21*z^211 - 10*z^210 + 22*z^209 - 29*z^207 - 19*z^206 + 6*z^205 + 5*z^204 - 12*z^203 + 15*z^202 + 12*z^201 - 3*z^200 - 6*z^199 + 14*z^198 - 6*z^197 - 4*z^196 + 11*z^195 - 9*z^194 - z^193 - 7*z^191 - 2*z^190 - 2*z^189 - 3*z^187 - 8*z^186 + 2*z^185 + 5*z^184 + 4*z^183 + 3*z^182 - 10*z^180 - 14*z^179 + 6*z^178 - 3*z^177 - 8*z^176 + 12*z^175 + 11*z^174 + z^173 - 2*z^172 - 13*z^171 - 24*z^170 + 2*z^168 - 11*z^167 + 6*z^166 + 7*z^165 + 8*z^164 - 8*z^163 + 5*z^162 - 9*z^161 + 4*z^160 + 7*z^159 + 9*z^158 - 2*z^157 - 7*z^156 + z^155 - 18*z^154 - 3*z^153 - 5*z^152 + 19*z^151 - z^150 - 3*z^149 - 2*z^148 - 13*z^147 + 3*z^146 - z^145 + 4*z^144 - 7*z^143 + 5*z^142 + z^141 - 3*z^140 - z^139 - z^138 - 16*z^137 - 13*z^136 + 10*z^135 + 14*z^134 + z^133 + 18*z^132 - 18*z^131 - 3*z^130 - 4*z^129 + 9*z^128 - 13*z^127 - z^126 + 4*z^125 + 3*z^124 + z^123 - 10*z^122 + 6*z^121 + 8*z^120 + 6*z^119 + 7*z^118 + 11*z^117 - 9*z^116 + 7*z^115 + 14*z^114 - 13*z^113 - 8*z^112 + 12*z^111 + 4*z^110 + 5*z^109 + 10*z^108 - 15*z^107 - 14*z^106 + 10*z^105 + 2*z^104 - z^103 - 13*z^102 + 12*z^101 + 7*z^100 + 4*z^99 - z^97 - 8*z^96 - 7*z^95 + 5*z^94 + 4*z^93 + 3*z^92 - 10*z^91 - 2*z^90 + 4*z^89 + 18*z^88 + 6*z^87 + 7*z^86 + 4*z^84 - 5*z^83 - 3*z^82 + 7*z^81 - 17*z^80 - 10*z^79 + 2*z^78 - 7*z^77 - 6*z^76 + 2*z^75 + z^74 - 15*z^73 + 14*z^72 + 14*z^71 - 6*z^70 + 16*z^69 + 6*z^68 + 2*z^67 - 4*z^66 + 5*z^65 - 10*z^64 + z^63 - 5*z^62 + 4*z^61 + z^60 - 5*z^59 + 5*z^58 + 8*z^57 - 2*z^56 - z^55 + 16*z^54 - 4*z^53 - 9*z^52 - 10*z^50 + 14*z^48 + z^47 - 21*z^46 - 6*z^45 + 15*z^44 + 9*z^43 + 4*z^42 + 11*z^41 + 4*z^40 - 6*z^39 + 2*z^37 - 15*z^36 + 3*z^35 + 13*z^34 + 7*z^33 - 14*z^32 - 9*z^31 - z^30 - 4*z^29 + 8*z^28 + 9*z^27 - z^26 - 6*z^25 + 19*z^24 + 14*z^23 - 15*z^22 + 4*z^21 + 4*z^20 - 5*z^19 + 4*z^18 + 14*z^17 + 8*z^16 + z^15 - 3*z^14 - 12*z^13 + 3*z^12 + 3*z^11 + 12*z^10 + 7*z^9 + 4*z^8 + 11*z^7 - z^6 - 10*z^5 + 7*z^4 - z^3 - 16*z^2 + 3*z + 13)"""# Compute the AES key
key = sha256(sk_str.encode()).digest()# Decrypt the flag
cipher = AES.new(key=key, mode=AES.MODE_CBC, iv=iv)
flag = unpad(cipher.decrypt(enc), 16)print(flag.decode())

Running the Solution

$ python3 solve.py
0xfun{tOO_LLL_256_B_kkkkKZ_t4e_f14g_F14g}

What Should Have Been Done (Intended Solution)

If the secret key hadn’t been leaked, the intended solution would likely involve:

1. Lattice Construction

From the partial leakage, construct a lattice that includes:

• The known coefficients of f and g
• The public key equations
• The NTRU relation fG - gF = 1

2. Lattice Reduction

Use LLL or BKZ algorithms to find short vectors in the lattice that correspond to the secret key:

from sage.all import *

# Construct lattice basis matrix
# Include known coefficients as constraints
# Include public key relationsL = Matrix(ZZ, basis)
L_reduced = L.LLL()  # or L.BKZ()# Extract secret key from short vector

3. Key Recovery

The shortest vector in the reduced lattice should correspond to the secret polynomials (f, g), allowing full secret key reconstruction.

Key Takeaways

For Challenge Creators

1. Never print secret keys in production code — This seems obvious, but it’s easy to leave debug statements
2. Sanitize outputs — Always review what’s being sent to users
3. Test your challenges — Have someone solve it as intended before release

For Attackers

1. Always check for information leakage — Sometimes the easiest solution is right in front of you
2. Read all output carefully — The vulnerability was in plain sight
3. Understand both the intended and unintended solutions — Learn from both paths

About HAWK

HAWK is an interesting post-quantum signature scheme with:

• Small signature sizes compared to other lattice schemes
• Fast signing operations
• Cyclotomic field structure providing algebraic properties
• Security based on Module-LWE and Module-SIS problems

References

• HAWK Specification (eprint.iacr.org/2019/015.pdf)
• NIST Post-Quantum Cryptography Standardization
• Lattice-Based Cryptography Resources

Flag

0xfun{tOO_LLL_256_B_kkkkKZ_t4e_f14g_F14g}