生成无法被猜测的唯一标识符

Question

我有一个系统需要安排一些任务并向某些外部对象返回这些任务的标识符。用户基本上需要执行以下操作：

identifier = MyLib.Schedule(something)
# Nah, let's unschedule it.
MyLib.Unschedule(identifier)

我在内部代码中经常使用这种模式，我总是使用普通整数作为标识符。但如果标识符被不受信任的代码使用，恶意用户可能通过执行单个Unschedule(randint())来破坏整个系统。

我需要代码的用户能够只取消已经安排的标识符。

我能想到的唯一解决方案是生成64位随机数作为标识符，并跟踪当前分配的标识符，以避免极不可能的重复。或者是128位？如果有的话，什么时候可以说“这已经足够随机了，不可能出现重复”，或者永远不可能？

或者更好的方法是什么？有没有一种方法可以生成标识符令生成器可以轻松跟踪（避免重复），但对接收者来说与随机数无法区分的标识符令牌？

编辑-基于被接受的答案的解决方案：

from Crypto.Cipher import AES
import struct, os, itertools

class AES_UniqueIdentifier(object):
    def __init__(self):
        self.salt = os.urandom(8)
        self.count = itertools.count(0)
        self.cipher = AES.new(os.urandom(16), AES.MODE_ECB)
    def Generate(self):
        return self.cipher.encrypt(self.salt + 
                                   struct.pack("Q", next(self.count)))
    def Verify(self, identifier):
        "Return true if identifier was generated by this object."
        return self.cipher.decrypt(identifier)[0:8] == self.salt

- porgarmingduod

---

大多数（伪）随机数生成器都允许您通过始终使用相同的种子初始化生成器来跟踪生成的内容。如果在同一台机器上使用它，那将产生完全相同的数字序列。因此，通过具有应该是恒定的种子和生成的标识符数量的计数器，您可以检查以前是否生成了任何给定的数字。这将是一种简单的方法，如果您可以重置标识符（例如当所有标识符都未安排时），则可能是可以接受的，但如果您需要跟踪大量数字，则会变得非常缓慢。 - Trinidad

实现Unschedule()的代码是否在一个安全系统中？这个系统不能被客户端检查吗？否则，您无法指望维护客户端无法发现的秘密值。 - President James K. Polk

@GregS：是的，基本上是这样。客户端代码旨在运行在沙盒中。 @Trinidad：系统需要能够处理大量数字。我会说每秒至少有10000个数字。（虽然取消预订应该是一个罕见事件）。 - porgarmingduod

Answer 1

根据您拥有的活动ID数量，64位可能太少了。根据生日悖论，您最终会得到从32位标识符中期望获得的保护水平。

此外，创建这些标识符的最佳方法可能是使用一些带有随机选择的盐（保密）的盐散列函数，例如SHA-1或MD5或您的框架已经拥有的任何内容，并且这些函数生成至少128位，正如上面提到的原因一样。如果您使用生成更长哈希值的函数，我真的看不到截断它们的任何理由。

要创建可在不存储它们的情况下检查的标识符，请使用易于检测的内容，例如两次相同的64位模式（总共128位），并使用AES或其他块大小为128位（或您选择的其他大小）的密码器使用某个常量秘密密钥进行加密。如果用户发送某个所谓的密钥，则解密并检查易于发现的模式。

- Christopher Creutzig

---

啊，太聪明了。我知道足够的密码学，强烈怀疑有一种直接的方法来签署我的生成标识符，但是没有足够的能力自己想出来。事实上，我的问题确实是“签署唯一生成的标识符”。 - porgarmingduod

Answer 2

听起来你可能在过度思考这个问题。这完全可以使用GUID/UUID应用程序解决。Python甚至有内置的生成方法。GUID/UUID的整个意义在于碰撞的几率是极小的，而且通过使用字符串而不是加密令牌，您可以跳过验证步骤中的解密操作。我认为这也将消除您可能遇到的关键管理问题，并提高整个过程的速度。

编辑：

使用UUID，您的验证方法只需比较给定的UUID和存储的UUID即可。由于两个UUID之间发生碰撞的几率极低，因此您不必担心误报。在您的示例中，似乎同一对象既进行加密又进行解密，而没有第三方读取存储的数据。如果是这种情况，那么传递加密数据除了传递的位数不易猜测外，您并没有获得任何好处。我认为UUID将为您提供相同的好处，而不需要加密操作的开销。

- TwentyMiles

---

Uuid 是一个有用的知识点，我将来肯定会用到它。谢谢。但是我不明白如何在验证步骤中“跳过解密操作”，因为我根本无法验证 UUID。这两种解决方案并不相同，它们满足不同的需求。我很高兴了解到这两种方法。 - porgarmingduod

当然可以通过存储UUID来验证它们，这是显而易见的。但这并不改变这两个具有不同特性的解决方案之间的差异。 - porgarmingduod

Answer 3

这与处理普通Web应用程序中的会话标识符是相同的问题。可预测的会话ID很容易导致会话劫持。

看一下会话ID是如何生成的。这里是典型PHPSESSID cookie的内容：

bf597801be237aa8531058dab94a08a9

如果你想要确保没有暴力攻击是可行的，可以反向计算：黑客每秒钟可以尝试多少次？在随机时间点使用了多少不同的唯一ID？总共有多少个ID？黑客需要多长时间才能覆盖总ID空间的1％？根据需要调整位数。

- aioobe

Answer 4

你需要在分布式环境还是本地环境中使用这个模式？

如果是本地环境，大多数面向对象的编程语言都应该支持对象标识的概念，因此如果你创建一个不透明的句柄 - 只需创建一个新对象即可。

handle = new Object(); // in Java

没有其他客户端可以伪造这个。

如果您需要在分布式环境中使用此功能，可以为每个会话保留句柄池，以便外部会话永远无法使用被盗的句柄。

- mtraut

Answer 5

你需要让你的标识符足够长，这样就不容易被猜到。此外，如果令牌没有在使用中，让Unschedule等待1秒钟，这样暴力攻击就不再可行了。正如其他答案所说，Web应用程序中的会话ID也是同样的问题，我已经看到过长度为64个随机字符的会话ID。

- Daniel