2009-01-22 33 views
29

Tôi đang cố gắng đối sánh văn bản chung của SHA1 với cụm từ thông dụng.Regex để khớp với SHA1

Lý tưởng nhất là tôi muốn tránh các từ phù hợp. An toàn để nói rằng toàn bộ SHA1 có một mẫu riêng biệt (chúng dài và có chiều dài nhất quán) - vì vậy tôi có thể phù hợp với những điều này một cách đáng tin cậy - nhưng những gì về SHA1 viết tắt thì sao?

Tôi có thể dựa vào sự hiện diện của các số không?

Nhìn vào SHA1 trong nhật ký cam kết của tôi - các số luôn xuất hiện trong 3 ký tự đầu tiên. Nhưng điều này quá ngắn? Tôi cần cân nhắc bao nhiêu ký tự của SHA1 trước khi tôi có thể giả định một số sẽ xuất hiện?

Điều này không nhất thiết phải chính xác 100% - tôi chỉ cần khớp với SHA1 viết tắt là 99% thời gian.

+0

Làm thế nào để SHA1 được đại diện? Thập phân? Hex? Cơ sở 64? Hàm băm chỉ là một con số thực sự lớn, và về mặt kỹ thuật, mỗi ký tự trong nó là một chữ số, nếu không phải là một 'số' theo nghĩa thông thường. Tôi nghĩ một số ví dụ sẽ thực sự tốt ở đây. –

+0

Hoặc có lẽ tôi chỉ là những thứ quá mức như bình thường. –

+0

FWIW - gần một thập kỷ sau - tất cả các băm trong 'git log' của tôi hiện có chữ cái trong ba ký tự đầu tiên – galois

Trả lời

55

Bạn có thể xem xét các băm SHA1 là hoàn toàn ngẫu nhiên, do đó điều này làm giảm khả năng xác suất. Xác suất mà một chữ số đã cho không phải là một số là 6/16 hoặc 0,375. Xác suất ba chữ số SHA1 không phải là số là 0.375 ** 3, hay 0.0527 (5% ish). Tại sáu chữ số, điều này giảm một lần nữa để 0,00278 (0,2%). Tại năm chữ số, xác suất của tất cả các chữ cái giảm xuống dưới 1% (bạn nói rằng bạn muốn phù hợp với 99% thời gian).

Thật dễ dàng đưa ra một biểu thức chính quy mà luôn luôn phù hợp với các giá trị SHA1:

\b[0-9a-f]{5,40}\b 

Tuy nhiên, điều này cũng có thể phù hợp với từ lăm thư hoàn toàn tốt, giống như "thêm" hoặc "mờ". Trong tệp /usr/share/dict/words của tôi, có một vài từ sáu chữ cái sẽ khớp với: "accede", "beaded", "bedded", "decade", "deface", "efface" và "facade" là rất có thể. Tại bảy chữ cái, chỉ có "hành động" mà dường như không xuất hiện trong văn xuôi. Tất cả phụ thuộc vào số lượng dương tính giả bạn có thể chịu đựng được, và những từ mà bạn có thể sẽ gặp phải thực sự là gì.

+6

Tại sao {5,40} và không {40}? –

+1

@sheepsimulator: Có lẽ vì nó phổ biến để viết tắt băm - mặc dù chiều dài viết tắt mặc định trong git đầu ra là 7, vì vậy bạn có thể khá an toàn đi đến '{7,40}' và có ít sai tích cực hơn. @Greg Hewgill: các từ/usr/share/dict của tôi cũng chứa "acceded", "defaced", "effaced" và "facaded" - và ba từ đầu tiên là phổ biến, ít nhất là tương đối so với deedeed! – Cascabel

+0

@ Jefromi: lạ, tệp 'words' của tôi chứa" undefaced "nhưng không" defaced "! Trên cả OS X và FreeBSD, cũng vậy. –

28

Chính xác thì bạn đang cố gắng làm gì? Bạn không cần phải phân tích cú pháp bất kỳ kết quả đầu ra git nào với chẩn đoán - bạn luôn có thể yêu cầu chính xác dữ liệu bạn cần.

Nếu bạn muốn kết hợp một đại diện hex đầy đủ của một tổng SHA1, hãy thử:

/\b([a-f0-9]{40})\b/ 

Đó là, một từ gồm 40 ký tự đó là một trong hai chữ số hoặc các chữ cái từ a tới f.

Nếu bạn chỉ có một vài ký tự và không biết chúng ở đâu, thì bạn hoàn toàn không may mắn. Có phải "e78fd98" là ID cam kết viết tắt không? Có lẽ, nhưng những gì về "1234567"? Đó có phải là ID cam kết không? Số vé có vấn đề? Một số làm cho một bài kiểm tra thất bại?

Không có ngữ cảnh, bạn thực sự không thể biết dữ liệu có ý nghĩa gì.

Để trả lời câu hỏi trực tiếp của bạn, không có thuộc tính SHA1 nào có thể làm cho ba ký tự đầu tiên (ở dạng thập lục phân). Bạn chỉ là may mắn, hoặc có lẽ không may mắn, tùy thuộc vào cách bạn nhìn vào nó.

+2

Đây là những gì bạn muốn, chính xác 40 ký tự chữ số thập phân luôn phù hợp hơn là câu trả lời được chấp nhận hiện tại có thể không hoạt động luôn. – Otto

4

Tôi sẽ giả sử bạn muốn khớp với đối sánh được in thập lục phân của một SHA1 và không chống lại 20 byte thô tương đương. Hơn nữa, tôi sẽ giả định rằng SHA1 trong câu hỏi chỉ sử dụng các chữ thường để biểu diễn các chữ số hex. Bạn sẽ phải điều chỉnh biểu thức chính quy nếu các yêu cầu của bạn khác nhau.

grep -o -E -e "[0-9a-f]{40}" 

Sẽ khớp với SHA1 như vậy. Bạn sẽ cần dịch cụm từ thông dụng ở trên từ phương ngữ của egrep sang bất kỳ công cụ nào bạn đang sử dụng. Vì trận đấu phải dài chính xác 40 ký tự, tôi không nghĩ rằng bạn đang gặp nguy hiểm với các từ trùng khớp ngẫu nhiên. Tôi không biết bất kỳ từ nào gồm 40 ký tự chỉ bao gồm các chữ cái từ a đến f.

chỉnh sửa:

Hơn thế nữa: sử dụng A Regex to match a SHA1 như giải pháp của ông bao gồm việc kiểm tra ranh giới từ ở cả hai đầu. Tôi bỏ qua điều đó ở trên.

2

Nếu bạn có quyền truy cập vào repo, bạn có thể sử dụng git cat-file -e để kiểm tra để chắc chắn rằng nó đại diện cho một đối tượng trong repo. Điều này cũng rất nhanh. Nếu bạn muốn hạn chế điều này chỉ với các cam kết và thẻ, bạn có thể sử dụng git cat-file -t để tìm ra loại đối tượng.

Điều này có thể được sử dụng, ví dụ: để tìm kiếm văn bản do con người tạo để đề cập đến các cam kết git và tạo siêu liên kết đến giao diện web git.

0

Đối với loại băm: 43:A4:02:B7:B6:1D:89:86:C5:CE:AD:52:96:D9:2E:7B:64:98:45:6A:

/^[0-9A-F]{2}(:[0-9A-F]{2}){19}$/ 
0

tôi sử dụng điều này trong ruby. Nó cho phép một phiên bản ngắn của sha (6-8 trong trường hợp xung đột) và cho toàn bộ sha tại 40 ký tự dài.

\A(([0-9a-f]{40})|([0-9a-f]{6,8}))\z 
+0

Vì bạn nói _ruby_, điều này sẽ ngắn hơn: '\ A ((\ h {40}) | (\ h {6}}) \ z', vì' \ h' là viết tắt của lớp ký tự thập lục phân. – Julien

Các vấn đề liên quan