足够安全的8位短的唯一随机字符串

60 人关注

我试图计算8个字符的短的唯一的随机文件名,比方说,成千上万的文件,没有可能的名称碰撞。这种方法是否足够安全?

base64.urlsafe_b64encode(hashlib.md5(os.urandom(128)).digest())[:8]

更清楚地说,我正试图实现对上传到存储器的文件名进行最简单的混淆。

我发现,如果实施得当,8个字符的字符串,足够随机,将是非常有效和简单的方式来存储数以万计的文件,而不会出现可能的碰撞。我不需要保证唯一性,只需要有足够高的名称碰撞概率(只谈成千上万的名称)。

文件被存储在并发环境中,所以增加共享计数器是可以实现的,但很复杂。在数据库中存储计数器将是低效的。

我还面临着这样一个事实:随机()在某些情况下会返回相同伪随机序列在different processes.

5 个评论
你说的 "足够安全",是指 "我根本不需要处理碰撞",还是 "碰撞会很不常见,即使我处理的效率不高也无所谓"?
rook
停止使用md5! 它是一个坏了的哈希函数,并且由于它的PRNG输出有问题而使输出的随机性降低。
@鲁克。+1.人们通常使用它是因为 "它比图书馆里的其他东西快得多,而且我不 真的 need secure hashes…" but of course if you don't 真的 need secure hashes, you don't need MD5 either, so why not just do urlsafe_b64encode(os.urandom(6)) in the first place?
@Rook 在这里使用MD5,虽然毫无意义,但不会增加碰撞率。
@PhilGan:你在那里写的是什么语言?
python
hash
random
cryptography
zahory
zahory
发布于 2012-11-21
8 个回答
arshajii
arshajii
发布于 2017-06-17
已采纳
0 人赞同

你目前的方法应该是足够安全的,但你也可以研究一下 uuid module. e.g.

import uuid
print str(uuid.uuid4())[:8]

Output:

ef21b9ad
    
注意, uuid4 的 "4 "部分非常重要。例如,"uuid1 "生成的字符串具有基于主机ID的固定前缀。
这给了我10万个名字中的3个碰撞。这可能是一个糟糕的方法,因为你只使用了16个字符。
我在其他地方读到,截断uuids并不是生成短的随机字符串的好方法。
@zahory:部分原因是BoppreH提出的观点。你必须了解每种类型的UUID是如何工作的,然后才能知道以不同方式截断它们有多安全。
在一百万人的名单上尝试时,有43981次碰撞。
Oleg
Oleg
发布于 2017-06-17
0 人赞同

Which method has less collisions, is faster and easier to read?

The random_choice is the 最快的 ,有 fewer collisions but is IMO slightly 更难读 .

The 最具可读性 shortuuid_random ,但属于外部依赖,而且速度稍慢,有6倍的碰撞。

The methods

alphabet = string.ascii_lowercase + string.digits su = shortuuid.ShortUUID(alphabet=alphabet) def random_choice(): return ''.join(random.choices(alphabet, k=8)) def truncated_uuid4(): return str(uuid.uuid4())[:8] def shortuuid_random(): return su.random(length=8) def secrets_random_choice(): return ''.join(secrets.choice(alphabet) for _ in range(8))

Results

所有方法都从 abcdefghijklmnopqrstuvwxyz0123456789 的字母表中生成8个字符的UUID。碰撞是根据1000万次抽签的单次运行计算的。时间以秒为单位,报告为平均函数执行时间±标准偏差,两者都是在100次运行1000次抽奖中计算出来的。总时间是碰撞测试的总执行时间。

random_choice: collisions 22 - time (s) 0.00229 ± 0.00016 - total (s) 29.70518
truncated_uuid4: collisions 11711 - time (s) 0.00439 ± 0.00021 - total (s) 54.03649
shortuuid_random: collisions 124 - time (s) 0.00482 ± 0.00029 - total (s) 51.19624
secrets_random_choice: collisions 15 - time (s) 0.02113 ± 0.00072 - total (s) 228.23106

Notes

  • the default shortuuid alphabet has uppercase characters, hence creating fewer collision. To make it a fair comparison we need to select the same alphabet as the other methods.
  • the secrets methods token_hex and token_urlsafe while possibly faster, have different alphabets, hence not eligible for the comparison.
  • the alphabet and class-based shortuuid methods are factored out as module variables, hence speeding up the method execution. This should not affect the TLDR.
  • Full testing details

    import random
    import secrets
    from statistics import mean
    from statistics import stdev
    import string
    import time
    import timeit
    import uuid
    import shortuuid
    alphabet = string.ascii_lowercase + string.digits
    su = shortuuid.ShortUUID(alphabet=alphabet)
    def random_choice():
        return ''.join(random.choices(alphabet, k=8))
    def truncated_uuid4():
        return str(uuid.uuid4())[:8]
    def shortuuid_random():
        return su.random(length=8)
    def secrets_random_choice():
        return ''.join(secrets.choice(alphabet) for _ in range(8))
    def test_collisions(fun):
        out = set()
        count = 0
        for _ in range(10_000_000):
            new = fun()
            if new in out:
                count += 1
            else:
                out.add(new)
        return count
    def run_and_print_results(fun):
        round_digits = 5
        now = time.time()
        collisions = test_collisions(fun)
        total_time = round(time.time() - now, round_digits)
        trials = 1_000
        runs = 100
        func_time = timeit.repeat(fun, repeat=runs, number=trials)
        avg = round(mean(func_time), round_digits)
        std = round(stdev(func_time), round_digits)
        print(f'{fun.__name__}: collisions {collisions} - '
              f'time (s) {avg} ± {std} - '
              f'total (s) {total_time}')
    if __name__ == '__main__':
        run_and_print_results(random_choice)
        run_and_print_results(truncated_uuid4)
        run_and_print_results(shortuuid_random)
        run_and_print_results(secrets_random_choice)
        
    Oleg
    @NamGVU shortuuid random.choices 慢一点,碰撞也多一点,但绝对更有可读性。
    Leo E
    Leo E
    发布于 2017-06-17
    0 人赞同

    你可以试试 shortuuid 图书馆。

    安装在:【替换代码0

    那么,这就很简单,因为:

    > import shortuuid
    > shortuuid.uuid()
    'vytxeTZskVKR7C7WgdSP3d'
        
    测试了 shortuuid.uuid()[:8] ,有1亿次抽奖,得到了0次碰撞。但似乎有一个速度牺牲
    并只是为了好玩。10亿次抽奖导致55次碰撞
    在我看来,这应该是被选中的答案!
    Nick
    我猜这是一个Base64编码的UUID,去掉了 = 的填充物?
    Nick
    我看到他们实际上在使用Base57,没有Base64中的任何非字母数字。很好!
    abarnert
    abarnert
    发布于 2017-06-17
    0 人赞同

    你有什么理由不使用 tempfile 来生成名字吗?

    mkstemp NamedTemporaryFile 这样的函数绝对能保证给你提供独特的名字;基于随机字节的任何东西都不会给你提供。

    如果出于某种原因,你实际上还不想创建文件(例如,你生成的文件名要在某个远程服务器或其他地方使用),你不可能做到完全安全,但 mktemp 仍然比随机名称安全。

    或者只是在某个 "足够全局 "的位置上保存一个48位的计数器,这样你就能保证在碰撞之前经历整个名称周期,而且你也能保证知道碰撞何时会发生。

    它们都更安全,更简单,而且比阅读 urandom 和做 md5 更有效率。

    如果你真的想生成随机名字, ''.join(random.choice(my_charset) for _ in range(8)) 也会比你正在做的事情更简单,而且更有效率。甚至 urlsafe_b64encode(os.urandom(6)) 也和MD5哈希值一样随机,而且更简单、更高效。

    加密随机性和/或加密哈希函数的唯一好处是避免了可预测性。如果这对你来说不是一个问题,为什么要为它付费?而且,如果你确实需要避免可预测性,你几乎肯定需要避免竞赛和其他更简单的攻击,所以避免 mkstemp NamedTemporaryFile 是一个非常糟糕的主意。

    更不用说,正如Root在评论中指出的,如果你需要安全,MD5实际上并不提供安全。

    我正在重命名被上传到同一个地方的文件,所以没有使用 tempfile 。替换代码1】对任何事情来说都足够独特,但太长了。我很确定8个字符应该足以存储成千上万的名字而不发生碰撞,但我不确定如何做到这一点。通过散列 urandom ,我试图实现更好的随机性。
    @zahory 一个UUID按什么标准是 "太长"?
    @NickJohnson 它太长了,不好看:)长的文件名在列表中看起来很丑。正如我之前写的,8个字符应该足以存储几百个随机的独特名字而不可能发生碰撞,我只是不知道什么是增加不可能性的最好方法。
    @zahory 如果你想要短,你应该使用一个计数器。根据生日悖论,一个随机产生的ID必须是 至少要有 在相同数量的标识符下,其长度是顺序标识符的两倍。
    根据我的测试, ''.join([random.choice(string.ascii_letters+string.digits+'-_') for ch in range(8)]) 在数以百万计的字符串中不会产生碰撞,而且也比编码urandom()有效得多。我决定采用这种方式。
    Ignas Kiela
    Ignas Kiela
    发布于 2017-06-17
    0 人赞同

    从 Python 3.6 开始,你可能应该使用 secrets 模块。 secrets.token_urlsafe() 似乎对你的情况很有效,而且它保证使用加密安全的随机源。

    Kade
    Kade
    发布于 2017-06-17
    0 人赞同

    我正在使用 哈希德 来把时间戳转换成唯一的ID。(如果你想的话,你甚至可以把它转换回一个时间戳)。

    这样做的缺点是如果你创建ID的速度太快,你会得到一个重复的ID。但是,如果你在生成这些ID时,中间有时间间隔,那么这就是一个选择。

    下面是一个例子。

    from hashids import Hashids
    from datetime import datetime
    hashids = Hashids(salt = "lorem ipsum dolor sit amet", alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890")
    print(hashids.encode(int(datetime.today().timestamp()))) #'QJW60PJ1' when I ran it
        
    YouJiacheng
    YouJiacheng
    发布于 2017-06-17
    0 人赞同

    Fastest Deterministic Method

    import random
    import binascii
    e = random.Random(seed)
    binascii.b2a_base64(random.getrandbits(48).to_bytes(6, 'little'), newline=False)
    

    Fastest System Random Method

    import os
    import binascii
    binascii.b2a_base64(os.urandom(6), newline=False)
    

    Url Safe Methods

    Use os.urandom

    import os
    import base64
    base64.urlsafe_b64encode(os.urandom(6)).decode()
    

    Use random.Random.choices (slow, but flexible)

    import random
    import string
    alphabet = string.ascii_letters + string.digits + '-_'
    ''.join(random.choices(alphabet, k=8))
    

    Use random.Random.getrandbits (faster than random.Random.randbytes)

    import random
    import base64
    base64.urlsafe_b64encode(random.getrandbits(48).to_bytes(6, 'little')).decode()
    

    Use random.Random.randbytes (python >= 3.9)

    import random
    import base64
    base64.urlsafe_b64encode(random.randbytes(6)).decode()
    

    Use random.SystemRandom.randbytes (python >= 3.9)

    import random
    import base64
    e = random.SystemRandom()
    base64.urlsafe_b64encode(e.randbytes(6)).decode()
    

    random.SystemRandom.getrandbits is not recommended if python >= 3.9, since it takes 2.5x time comparing to random.SystemRandom.randbytes and is more complicated.

    Use secrets.token_bytes (python >= 3.6)

    import secrets
    import base64
    base64.urlsafe_b64encode(secrets.token_bytes(6)).decode()
    

    Use secrets.token_urlsafe (python >= 3.6)

    import secrets
    secrets.token_urlsafe(6) # 6 byte base64 has 8 char
    

    Further Discussion

    secrets.token_urlsafe在python3.9中的实现

    tok = token_bytes(nbytes)
    base64.urlsafe_b64encode(tok).rstrip(b'=').decode('ascii')
    

    Since ASCII bytes .decode() is faster than .decode('ascii'), and .rstrip(b'=') is useless when nbytes % 6 == 0.

    base64.urlsafe_b64encode(secrets.token_bytes(nbytes)).decode() is faster (~20%).

    在Windows10上,当nbytes=6(8个字符)时,基于字节的方法快2倍,而当nbytes=24(32个字符)时,快5倍。

    在Windows 10(我的笔记本电脑)上,secrets.token_bytes花费的时间与random.Random.randbytes相似,而base64.urlsafe_b64encode比随机字节生成花费的时间更多。

    在Ubuntu 20.04(我的云服务器,可能缺乏熵)上,secrets.token_bytesrandom.Random.randbytes多花了15倍的时间,但与random.SystemRandom.randbytes的时间相近。

    由于secrets.token_bytes使用random.SystemRandom.randbytes使用os.urandom(因此它们是完全相同的),如果性能至关重要,你可以用os.urandom代替secrets.token_bytes

    在Python3.9中,base64.urlsafe_b64encodebase64.b64encodebytes.translate的组合,因此多花了~30%的时间。

    random.Random.randbytes(n) is implemented by random.Random.getrandbits(n * 8).to_bytes(n, 'little'), thus 3x slower. (However, random.SystemRandom.getrandbits is implemented with random.SystemRandom.randbytes)

    base64.b32encodebase64.b64encode慢得多(6个字节是5倍,480个字节是17倍),因为base64.b32encode中有很多python代码,而base64.b64encode只是调用binascii.b2a_base64(C实现)。

    但是,在base64.b64encode中有一个python分支语句if altchars is not None:,在处理小数据时,会引入不可忽略的开销,binascii.b2a_base64(data, newline=False)可能会更好。

    Sarath Ak
    Sarath Ak
    发布于 2017-06-17
    0 人赞同

    你可以试试这个

    import random
    uid_chars = ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u',
                 'v', 'w', 'x', 'y', 'z','1','2','3','4','5','6','7','8','9','0')
    uid_length=8
    def short_uid():
        count=len(uid_chars)-1
        for i in range(0,uid_length):
            c+=uid_chars[random.randint(0,count)]
        return c