มีความเสี่ยงที่บางนิพจน์ในฟังก์ชันแฮชสามารถย้อนกลับได้หรือไม่?

ฉันได้พัฒนาแอปพลิเคชันที่ย้อนกลับนิพจน์บางอย่างที่ใช้ในอัลกอริทึมแฮช แอปพลิเคชันไม่ได้ย้อนกลับอัลกอริทึมทั้งหมด แต่จะย้อนกลับบางส่วน แอปพลิเคชั่นนี้แสดงให้เห็นว่าการแสดงออกบางอย่างในอัลกอริทึมสามารถย้อนกลับได้ สิ่งนี้ก่อให้เกิดความเสี่ยงต่อแฮชอัลกอริทึมที่ใช้นิพจน์ที่คล้ายกันหรือไม่

ด้านล่างนี้คือผลลัพธ์ของแอปพลิเคชันและโค้ดทดสอบของนิพจน์ที่สร้างขึ้นจากนิพจน์ที่ใช้บ่อยในอัลกอริทึมแฮช จะเห็นว่าแต่ละคีย์ให้ค่าแฮชเท่ากันเมื่อทดสอบสำหรับนิพจน์ทั้งหมดของความซับซ้อนนี้ (การดำเนินการระดับบิตเท่านั้น) แอปพลิเคชันสามารถแสดงรายการคีย์ที่เป็นไปได้ทั้งหมดสำหรับแต่ละค่าแฮช

ผลลัพธ์ของแอปพลิเคชัน:

 แฮช: 817621565b0d4457402862cee209f1ab139bbd8caf2dc72ec172d4d90429c409
 
รายการคีย์ (3)
 --------------------------------------------- ------------------------
  1 คีย์: 37639fed3f5c6b60c38a1aeb3589f3176e2b965d75b6a1214ec96b34ddebe005
  2 รหัส: e23aab653bfe6aa1591496d880687ef17624366a6db9a4159e1bd4dfa879aad9
  3 คีย์: 249d8cca4a00491c20af4cb0ba8d273518162e6ebddbfc2e243355fbfa179089
 --------------------------------------------- ------------------------

รหัสทดสอบ:

#รวม <stdio.h>
#รวม <stdlib.h>


#define MAJ(x,y,z) (((x) & (y)) ^ ((x) & (z)) ^ ((y) & (z)))
#กำหนด ROTBYTE(x, y) (((x) << (y)) | ((x) >> ((8) - (y))))



// อัลกอริทึมแฮช
int Prs (อินพุต char * ที่ไม่ได้ลงชื่อ, int input_len, char * เอาต์พุตที่ไม่ได้ลงชื่อ, int output_len) {
    int ฉัน;

    ถ่านที่ไม่ได้ลงชื่อ pn[32] = {113,232,143,101, 58, 79,137, 10,145, 88,110, 97,203, 35,241,171,
                            221,156, 88, 39,122, 91,105,145,253,103,165, 26,197, 96, 74,131};

    สำหรับ (i=0; i<output_len; i++) {
        เอาต์พุต[i]=pn[i%32]^ROTBYTE(อินพุต[i%input_len],2)^ROTBYTE(อินพุต[(i+1)%input_len],3);
        เอาต์พุต[i]^=MAJ(อินพุต[(i)%input_len],อินพุต[(i+1)%input_len],อินพุต[(i+2)%input_len]);
    }

    กลับ 0;
}


int HexToBin (ถ่าน m ที่ไม่ได้ลงนาม, ถ่านที่ไม่ได้ลงนาม, ถ่านที่ไม่ได้ลงนาม * r) {
    ถ่านที่ไม่ได้ลงชื่อ v;
    ถ้า (m>='a' && m<='f') {
        v=(m-'a'+10)<<4;
    }อื่นถ้า (m>='A' && m<='F') {
        v=(m-'A'+10)<<4;
    } อื่นถ้า(m>='0' && m<='9') {
        v=(m-'0')<<4;
    }อื่น{
        กลับ 1;
    }

    ถ้า (l>='a' && l<='f') {
        v|=(l-'a'+10);
    } อื่นถ้า (l>='A' && l<='F') {
        v|=(l-'A'+10);
    } อื่นถ้า (l>='0' && l<='9') {
        v|=(ล-'0');
    }อื่น{
        กลับ 1;
    }
    *r=v;
    กลับ 0;
}


int HexToBinArray (ถ่านที่ไม่ได้ลงชื่อ * src, int len, ถ่านที่ไม่ได้ลงชื่อ * ออก) {
    int ฉัน;
    สำหรับ (i=0; i<len; i++) {
        ถ้า(HexToBin(src[i*2],src[i*2+1],&ออก[i])){
            กลับ 1;
        }
    }
    กลับ 0;
}


int BinToHex (ถ่านที่ไม่ได้ลงชื่อ b) {
    int v;
    ถ้า((b>>4)>=10) {
        v=((b>4)+'a'-10)<<8;
    } อื่น {
        v=((b>4)+'0')<<8;
    }

    ถ้า((b&15)>=10) {
        v|=((b&15)+'a'-10);
    } อื่น {
        v|=((b&15)+'0');
    }

    กลับ v;

}


เป็นโมฆะ BinToHexArray (ถ่านที่ไม่ได้ลงชื่อ * ใน, int len, ถ่านที่ไม่ได้ลงชื่อ * ออก) {
    int ฉัน;
    int v;
    สำหรับ (i=0; i<len; i++) {
        v=BinToHex(ใน[i]);
        ออก[i*2]=v>>8;
        ออก[i*2+1]=v&0xff;
    }
    ออก[i*2]=0;
    กลับ;
}


int Slen (ถ่าน * s) {
    ถ่าน * t;
    เสื้อ = s;
    ในขณะที่ (* วินาที)
        s++;
    กลับ s-t;
}


int หลัก () {
    int input_len=32;
    int output_len=32;
    รหัสถ่านที่ไม่ได้ลงชื่อ [32];
    แฮชถ่านที่ไม่ได้ลงชื่อ [32];
    ถ่านที่ไม่ได้ลงชื่อ [1024];
    int สเลน;



    ในขณะที่ (1) {
            ทำ{
                printf("\n\n\n");
                printf(" ------8------16------24------32------40------48--- ---56------64 \n");
                printf(" | | | | | | | | \n");
                printf(" คีย์ : ");
                scanf("%s",บัฟ);
                slen=สเลน(บัฟ);
                ถ้า(slen!=input_len*2){
                    printf("ความยาวของคีย์ต้องเป็นเลขฐานสิบหก %d หลัก",input_len*2);
                }
            }ในขณะที่(slen!=input_len*2);

        // แปลงสตริงฐานสิบหกเป็นไบนารี
        ถ้า (HexToBinArray (บัฟ, input_len, คีย์)) {
            printf(" อักขระต่างประเทศในเลขฐานสิบหก \n");
            ดำเนินต่อ;
        }

        // อัลกอริทึมแฮช
        Prs(คีย์,input_len,แฮช,output_len);

        // แปลงไบนารีเป็นสตริงฐานสิบหก
        BinToHexArray(แฮช,input_len,buf);
        printf("แฮช : %s\n",buf);
    }


    กลับ 0;
}

โค้ดทดสอบเขียนขึ้นเพื่อทดสอบความถูกต้องของเอาต์พุตแอปพลิเคชันเท่านั้น ในโค้ดอัลกอริทึมแฮชอยู่ในฟังก์ชัน "Prs" ฟังก์ชันอื่นๆ จำเป็นสำหรับโค้ดในการทำงาน แต่ไม่สำคัญ คำนวณรหัสแฮชของค่าคีย์ขนาด 32 ไบต์ที่เขียนในลูปไม่สิ้นสุดเมื่อโค้ดถูกคอมไพล์และดำเนินการ เมื่อทดสอบคีย์ข้างต้นแล้ว การค้นหาค่าแฮชที่เหมือนกันสำหรับแต่ละคีย์จะพิสูจน์ว่านิพจน์ในฟังก์ชัน "Prs" นั้นกลับรายการ

แอปพลิเคชั่นนี้แสดงให้เห็นว่านิพจน์บางอย่างในอัลกอริทึมสามารถย้อนกลับได้"

เป็นที่ทราบกันดีว่าโค้ดส่วนใหญ่ใน SHA-2, SHA-3 สามารถย้อนกลับได้

ฟังก์ชันบีบอัดแฮช SHA-2 $h(s,m) = s + f_m(s)$, ที่ไหน $f_m(s)$ จะเปลี่ยนกลับเป็นบล็อกข้อความแบบตายตัวได้ $m$ [1][2] - นั่นคือถ้าคุณรู้อะไร $m$ เป็นและสิ่งที่คุณต้องการค่า $f_m(s)$ เป็นเรื่องง่ายที่จะหาสถานะเริ่มต้น $s$ ที่ได้คุณค่านั้นมา ฟังก์ชันแฮชบัญชีสำหรับสิ่งนี้โดยรวม $+$ การดำเนินการซึ่งไม่สามารถย้อนกลับได้ (เนื่องจากทั้งสองฝ่ายขึ้นอยู่กับสถานะก่อนหน้า $s$ดังนั้นผู้โจมตีจึงไม่สามารถย้อนกลับการดำเนินการบีบอัดแฮชทั้งหมดได้)

ด้วย SHA-3 การเปลี่ยนแปลงสถานะทั้งหมดจะกลับด้านได้ นั่นคือ ถ้าคุณทราบสถานะเป้าหมาย 1600 บิต การคำนวณสถานะก่อนหน้าที่จะแปลงเป็นสถานะนั้นจะทำได้ง่าย ฟังก์ชันแฮชคำนึงถึงสิ่งนี้โดยเพิ่มขนาดของ 'ความจุ' เป็นสองเท่า (ส่วนของสถานะภายในที่ผู้โจมตีไม่สามารถควบคุมได้โดยตรง) ซึ่งหมายความว่าการโจมตีแบบ 'พบกันตรงกลาง' กับพรีอิมเมจนั้นไม่ง่ายไปกว่าการโจมตีด้วยกำลังเดรัจฉาน

ไม่นำไปสู่ช่องโหว่ที่รู้จัก

[1]: ฟังก์ชันการบีบอัดแฮชจะแตกต่างกันระหว่าง SHA-256 และ SHA-512 อย่างไรก็ตาม ข้อความนี้เป็นจริงสำหรับทั้งสอง

[2]: การดำเนินการเพิ่ม $+$ เป็นการเพิ่มโมดูลาร์ตามองค์ประกอบของเวกเตอร์ที่มีค่า 32 บิตหรือ 64 บิต