• ข้อความนั้นเรียกว่าคำพูดที่มีความหมาย${\displaystyle w}$และความยาว${\displaystyle n}$หากประกอบด้วย${\displaystyle n}$บิตและแน่นอน${\displaystyle w}$ในจำนวนนั้นมีเลขหนึ่งอยู่ด้วย
• คำที่มีน้ำหนัก${\displaystyle w}$และความยาว${\displaystyle n}$เรียกว่าปกติถ้าในทุกช่วงเวลา${\displaystyle [(i-1)(n/w),i(n/w))}$ประกอบด้วยค่าที่ไม่เป็นศูนย์เพียงค่าเดียวสำหรับทุกรายการ${\displaystyle 0<i<w+1}$กล่าวโดยสรุปแล้ว นั่นหมายความว่า หากเราแบ่งข้อความออกเป็นwส่วนเท่าๆ กัน แต่ละส่วนจะมีค่าที่ไม่เป็นศูนย์อยู่หนึ่งค่าพอดี

มีอยู่จำนวนที่แน่นอน${\displaystyle (n/w)^{w}}$คำศัพท์ทั่วไปที่แตกต่างกันเกี่ยวกับน้ำหนัก${\displaystyle w}$และความยาว${\displaystyle n}$ดังนั้นเราจึงต้องการอย่างแม่นยำ${\displaystyle \log((n/w)^{w})=w\log(n/w)=s}$บิตข้อมูลเพื่อเข้ารหัสคำปกติเหล่านี้ เรากำหนดการจับคู่แบบหนึ่งต่อหนึ่งจากเซตของสตริงบิตที่มีความยาว${\displaystyle s}$ไปยังชุดคำปกติที่มีน้ำหนัก${\displaystyle w}$และความยาว${\displaystyle n}$จากนั้นฟังก์ชันการบีบอัด FSB จะถูกกำหนดดังต่อไปนี้ :

1. อินพุต: ข้อความที่มีขนาด${\displaystyle s}$
2. แปลงเป็นคำที่มีความยาวปกติ${\displaystyle n}$และน้ำหนัก${\displaystyle w}$
3. คูณด้วยเมทริกซ์${\displaystyle H}$
4. ผลลัพธ์: แฮชขนาด${\displaystyle r}$

โดยทั่วไปแล้วเวอร์ชันนี้เรียกว่าการบีบอัดตามกลุ่มอาการ (syndrome-based compression ) มันช้ามากและในทางปฏิบัติจะทำในวิธีที่แตกต่างและเร็วกว่า ทำให้เกิดการบีบอัดตามกลุ่มอาการแบบเร็ว (fast syndrome-based compression ) เราแยกออก${\displaystyle H}$ลงในเมทริกซ์ย่อย${\displaystyle H_{i}}$ขนาด${\displaystyle r\times n/w}$และเรากำหนดการจับคู่แบบหนึ่งต่อหนึ่งจากสตริงบิตที่มีความยาว${\displaystyle w\log(n/w)}$ไปยังชุดลำดับของ${\displaystyle w}$ตัวเลขระหว่าง 1 และ${\displaystyle n/w}$นี่เทียบเท่ากับการจับคู่แบบหนึ่งต่อหนึ่งกับเซตของคำปกติที่มีความยาว${\displaystyle n}$และน้ำหนัก${\displaystyle w}$เนื่องจากเราสามารถมองคำดังกล่าวเป็นลำดับตัวเลขระหว่าง 1 ถึง 2 ได้${\displaystyle n/w}$ฟังก์ชันการบีบอัดมีลักษณะดังนี้:

1. อินพุต: ข้อความขนาด${\displaystyle s}$
2. แปลง${\displaystyle s}$ไปยังลำดับของ${\displaystyle w}$ตัวเลข${\displaystyle s_{1},\dots ,s_{w}}$ระหว่าง 1 และ${\displaystyle n/w}$
3. บวกคอลัมน์ที่ตรงกันของเมทริกซ์เข้าด้วยกัน${\displaystyle H_{i}}$เพื่อให้ได้สตริงไบนารีที่มีความยาว${\displaystyle r}$
4. ผลลัพธ์: แฮชขนาด${\displaystyle r}$

ขณะนี้เราสามารถใช้การสร้างแบบ Merkle–Damgårdเพื่อขยายฟังก์ชันการบีบอัดให้สามารถรับอินพุตที่มีความยาวใดๆ ก็ได้

สถานการณ์และการเริ่มต้น : เข้ารหัสข้อความ${\displaystyle s=010011}$โดยใช้${\displaystyle 4\times 12}$เมทริกซ์ H ${\displaystyle H=\left({\begin{array}{llllcllllcllll}1&0&1&1&~&0&1&0&0&~&1&0&1&1\\0&1&0&0&~&0&1&1&1&~&0&1&0&0\\0&1&1&1&~&0&1&0&0&~&1&0&1&0\\1&1&0&0&~&1&0&1&1&~&0&0&0&1\end{array}}\right)}$ ซึ่งแยกออกเป็น${\displaystyle w=3}$บล็อกย่อย${\displaystyle H_{1}}$,${\displaystyle H_{2}}$,${\displaystyle H_{3}}$.

อัลกอริทึม :

1. เราแยกอินพุตออก${\displaystyle s}$เข้าไปข้างใน${\displaystyle w=3}$ส่วนของความยาว${\displaystyle \log _{2}(12/3)=2}$และเราได้รับ${\displaystyle s_{1}=01}$,${\displaystyle s_{2}=00}$,${\displaystyle s_{3}=11}$.
2. เราแปลงแต่ละอัน${\displaystyle s_{i}}$แปลงเป็นจำนวนเต็มแล้วได้ผลลัพธ์${\displaystyle s_{1}=1}$,${\displaystyle s_{2}=0}$,${\displaystyle s_{3}=3}$.
3. จากเมทริกซ์ย่อยแรก${\displaystyle H_{1}}$เราเลือกคอลัมน์ที่ 2 จากเมทริกซ์ย่อยที่สอง${\displaystyle H_{2}}$คอลัมน์ที่ 1 และจากเมทริกซ์ย่อยที่สาม คอลัมน์ที่ 4
4. เราบวกคอลัมน์ที่เลือกเข้าด้วยกันและได้ผลลัพธ์${\displaystyle r=0111\oplus 0001\oplus 1001=1111}$.

ดังที่กล่าวไว้ก่อนหน้านี้ ความปลอดภัยของ FSB ขึ้นอยู่กับปัญหาที่เรียกว่าการถอดรหัสซินโดรมแบบปกติ (RSD)การถอดรหัสซินโดรมเป็นปัญหาจากทฤษฎีการเข้ารหัสแต่เนื่องจากมันเป็นปัญหา NP-completeness จึงทำให้มันเป็นแอปพลิเคชันที่ดีสำหรับวิทยาการเข้ารหัสลับ การถอดรหัสซินโดรมแบบปกติเป็นกรณีพิเศษของการถอดรหัสซินโดรมและมีนิยามดังนี้:

นิยามของ RSD: กำหนดให้${\displaystyle w}$เมทริกซ์${\displaystyle H_{i}}$ของมิติ${\displaystyle r\times (n/w)}$และเชือกเส้นเล็กๆ${\displaystyle S}$ความยาว${\displaystyle r}$โดยที่ชุดหนึ่งมีอยู่${\displaystyle w}$คอลัมน์ละหนึ่งคอลัมน์${\displaystyle H_{i}}$รวมกันได้เป็น${\displaystyle S}$จงหาชุดคอลัมน์ดังกล่าว

ปัญหานี้ได้รับการพิสูจน์แล้วว่าเป็นปัญหาNP-completeโดยการลดรูปจากการจับคู่แบบ 3 มิติอย่างไรก็ตาม แม้ว่าจะไม่ทราบว่ามี อัลกอริทึม เวลาพหุนามสำหรับแก้ปัญหา NP-complete หรือไม่ แต่ก็ยังไม่มีอัลกอริทึมใดที่ค้นพบ และการค้นพบอัลกอริทึมดังกล่าวจะเป็นการค้นพบครั้งสำคัญ

เห็นได้ชัดว่าการค้นหาภาพต้นแบบของแฮชที่กำหนดนั้นทำได้ง่าย${\displaystyle S}$เทียบเท่ากับปัญหานี้อย่างแท้จริง ดังนั้นปัญหาการค้นหาภาพต้นแบบใน FSB จึงต้องเป็นปัญหา NP-complete เช่นกัน

เรายังต้องพิสูจน์ความต้านทานต่อการชนกัน สำหรับเรื่องนี้เราต้องการ RSD รูปแบบ NP-complete อีกแบบหนึ่ง นั่นคือการถอดรหัสซินโดรมว่างแบบ 2-regular

นิยามของ 2-RNSD: กำหนดให้${\displaystyle w}$เมทริกซ์${\displaystyle H_{i}}$ของมิติ${\displaystyle r\times (n/w)}$และเชือกเส้นเล็กๆ${\displaystyle S}$ความยาว${\displaystyle r}$โดยที่ชุดหนึ่งมีอยู่${\displaystyle w'}$คอลัมน์ โดยแต่ละคอลัมน์มีสองหรือศูนย์คอลัมน์${\displaystyle H_{i}}$รวมกันแล้วได้ศูนย์${\displaystyle (0<w'<2w)}$จงหาชุดคอลัมน์ดังกล่าว

นอกจากนี้ 2-RNSD ยังได้รับการพิสูจน์แล้วว่าเป็นปัญหาNP-completeโดยการลดรูปจากการจับคู่แบบ 3มิติ

เช่นเดียวกับที่ RSD นั้นโดยพื้นฐานแล้วเทียบเท่ากับการค้นหาคำธรรมดาๆ คำหนึ่ง${\displaystyle w}$โดยที่${\displaystyle Hw=S}$2-RNSD เทียบเท่ากับการค้นหาคำปกติ 2 ตัว${\displaystyle w'}$โดยที่${\displaystyle Hw'=0}$คำปกติ 2 คำที่มีความยาว${\displaystyle n}$และน้ำหนัก${\displaystyle w}$เป็นสตริงบิตที่มีความยาว${\displaystyle n}$โดยที่ในทุกช่วงเวลา${\displaystyle [(i-1)w,iw)}$ค่าของตัวเลขสองค่าหรือศูนย์ค่าจะมีค่าเท่ากับ 1 โปรดทราบว่า คำปกติ 2 ค่า คือผลรวมของคำปกติสองคำ

สมมติว่าเราพบการชนกันแล้ว ดังนั้นเราจะมี Hash( m ) = Hash( m ) โดยที่${\displaystyle m_{1}\neq m_{2}}$จากนั้นเราก็สามารถหาคำปกติสองคำได้${\displaystyle w_{1}}$และ${\displaystyle w_{2}}$โดยที่${\displaystyle Hw_{1}=Hw_{2}}$จากนั้นเราก็มี${\displaystyle H(w_{1}+w_{2})=Hw_{1}+Hw_{2}=2Hw_{1}=0}$;${\displaystyle (w_{1}+w_{2})}$เป็นผลรวมของคำปกติสองคำที่แตกต่างกัน ดังนั้นจึงต้องเป็นคำปกติ 2 คำที่มีแฮชเป็นศูนย์ ดังนั้นเราจึงแก้ปัญหาตัวอย่างของ 2-RNSD ได้แล้ว เราสรุปได้ว่าการค้นหาการชนกันใน FSB นั้นยากพอๆ กับการแก้ปัญหา 2-RNSD และดังนั้นจึงต้องเป็นปัญหา NP-complete

FSB เวอร์ชันล่าสุดใช้ฟังก์ชันการบีบอัดWhirlpoolเพื่อบีบอัดผลลัพธ์แฮชเพิ่มเติม แม้ว่าจะไม่สามารถพิสูจน์ได้ แต่ผู้เขียนโต้แย้งว่าการบีบอัดครั้งสุดท้ายนี้ไม่ได้ลดความปลอดภัยลง โปรดทราบว่าแม้ว่าจะสามารถค้นหาการชนกันใน Whirlpool ได้ ก็ยังคงต้องค้นหาภาพก่อนหน้าของการชนกันในฟังก์ชันการบีบอัด FSB ดั้งเดิมเพื่อค้นหาการชนกันใน FSB

ในการแก้ RSD เราจะอยู่ในสถานการณ์ตรงกันข้ามกับการแฮช โดยใช้ค่าเดียวกันกับในตัวอย่างก่อนหน้านี้ เราจะได้รับ${\displaystyle H}$แยกออกเป็น${\displaystyle w=3}$บล็อกย่อยและสตริง${\displaystyle r=1111}$เราได้รับมอบหมายให้หาคอลัมน์เพียงหนึ่งคอลัมน์ในแต่ละบล็อกย่อย ซึ่งผลรวมของคอลัมน์ทั้งหมดจะเท่ากับ...${\displaystyle r}$คำตอบที่คาดหวังจึงเป็นดังนี้${\displaystyle s_{1}=1}$,${\displaystyle s_{2}=0}$,${\displaystyle s_{3}=3}$เป็นที่ทราบกันดีว่าการคำนวณวิธีนี้ทำได้ยากสำหรับเมทริกซ์ขนาดใหญ่

ใน 2-RNSD เราต้องการค้นหาในแต่ละซับบล็อก ไม่ใช่แค่คอลัมน์เดียว แต่เป็นสองคอลัมน์หรือศูนย์คอลัมน์ ที่ผลรวมของคอลัมน์เหล่านั้นจะได้ 0000 (และไม่ใช่ 0)${\displaystyle r}$ในตัวอย่างนี้ เราอาจใช้คอลัมน์ (นับจาก 0) ที่ 2 และ 3 จาก${\displaystyle H_{1}}$ไม่มีคอลัมน์จาก${\displaystyle H_{2}}$คอลัมน์ที่ 0 และ 2 จาก${\displaystyle H_{3}}$ยังมีวิธีแก้ปัญหาอื่นๆ อีก เช่น อาจไม่มีการใช้คอลัมน์ใดๆ เลย${\displaystyle H_{3}}$.

ความปลอดภัยที่พิสูจน์ได้ของ FSB หมายความว่าการค้นหาการชนกันนั้นเป็นปัญหา NP-complete แต่การพิสูจน์นั้นเป็นการลดรูปไปสู่ปัญหาที่มีความซับซ้อนในกรณีที่เลวร้ายที่สุด แบบ asymptotically hard ซึ่งให้การรับประกันความปลอดภัยที่จำกัดเท่านั้น เนื่องจากยังคงมีอัลกอริทึมที่สามารถแก้ปัญหาได้อย่างง่ายดายสำหรับส่วนย่อยของพื้นที่ปัญหา ตัวอย่างเช่น มี วิธี การเชิงเส้นที่สามารถใช้สร้างการชนกันได้ในเวลาไม่กี่วินาทีบนพีซีเดสก์ท็อปสำหรับ FSB รุ่นแรกๆ ที่อ้างว่ามีความปลอดภัย 2^128 แสดงให้เห็นว่าฟังก์ชันแฮชให้ความต้านทานต่อภาพก่อนหน้าหรือการชนกันน้อยที่สุดเมื่อเลือกพื้นที่ข้อความในลักษณะเฉพาะ

ตารางต่อไปนี้แสดงความซับซ้อนของการโจมตีที่รู้จักกันดีที่สุดต่อ FSB