Megamos加密算法的规范

#1 楼

正如网络长官在他的回答中指出的那样，法院的判决书本身很有趣。特别是，虽然“ Megamos算法”本身的详细信息显然没有在法院判决中给出，但在第4段和第5段中以惊人的清晰方式描述了使用它的方式： “详细地说，其工作方式如下：汽车计算机和应答器都知道一个秘密号码。该号码是该汽车所独有的。它被称为“秘密密钥”。汽车计算机和应答器都还知道一个秘密密码。秘密算法。这是一个复杂的数学公式。给定两个数字，它将产生第三个数字。对于使用Megamos Crypto芯片的所有汽车，该算法都是相同的。 >“当过程开始时，汽车会产生一个随机数。它会被发送到应答器。现在，两台计算机都使用他们都应该知道的两个数字来执行复杂的数学运算，这两个数字都是随机数和密钥。它们各自产生第三个数字。该数字分为两个部分，分别称为F和G，这两个计算机现在都知道F和G。汽车将其F发送到应答器，应答器可以检查汽车是否正确计算了F。包括密钥和Megamos Crypto算法，现在可以使发送应答器确信汽车确实是应该的汽车，如果发送应答器满意，则发送应答器将G发送给汽车，汽车检查G是否正确。如果正确，则汽车对发送应答器也知道秘密密钥和Megamos Crypto算法感到满意，从而可以使汽车对发送应答器是真实的感到满意，因此这两个设备都无需另外确认设备的身份实际上揭示了秘密密钥或秘密算法。汽车可以安全地启动。在此过程中，身份验证取决于共享的秘密知识。为了确保过程的安全，信息的两个部分都需要保密-密钥和算法。“

（转换为标准加密术语），看来“ Megamos算法”是一种（显然失败了）尝试实现伪随机函数族（PRF）。
具体来说，以上各节中描述的身份验证协议可以表述为：

车载计算机$ \ rm C $和应答器$ \ rm T $拥有一个共享密钥$ K $和一个伪随机函数族（使用Megamos算法实现）$ \ sf PRF $，其中$ {\ sf PRF} _K $是特定实例由密钥$ K $参数化。PRF输出一个分成两个部分的位串$ F $和$ G $要执行身份验证交换，请执行以下操作：$ \ rm C $选择一个随机数$ r $并计算$（F，G）= {\ sf PRF} _K（r）$。
$ {\ rm C \ to T：} \ r，F $

$ \ rm T $计算$（F'，G'）= {\ sf PRF} _K（r）$并中止，除非$ F = F'$。
$ { \ rm T \ to C：} \ G'$

$ \ rm C $验证$ G = G'$。

现在$ \ rm C $和$ \ rm T $已验证它们每个都可以计算$ {\ sf PRF} _K $，因此拥有相同的密钥$ K $。

该协议的一个有趣特征是，由于$ r $仅由$ \ rm C $选择，设法窃听合法交易所的攻击者可以通过重播较早的$ r $和$ F $来轻松模拟$ \ rm C $，甚至可以验证$ \ rm T $的响应，方法是将其与之前的$ G $进行比较。在预期的使用情况下，这可能不会被视为主要的安全风险，因为重要的部分可能是将$ \ rm T $认证为$ \ rm C $。另一方面，由于该协议显然确实也尝试将$ \ rm C $认证为$ \ rm T $，因此可能只是上面的摘要不完整，并且实际协议使用了一些其他机制来防止这种重放
也就是说，除了上述缺陷之外，如果$ \ sf PRF $确实是一个安全的伪随机函数族，则该协议看起来很可靠。尤其是在法院的判决中，断言“为了确保程序的安全性，两个信息都必须保密-密钥和算法”显然是错误的：如果算法是安全的PRF，例如，例如AES-CMAC-PRF-128，只要保持密钥$ K $的安全，上述协议就是安全的。
确实，无论协议的细节如何，情况都是一样的：根据定义，安全伪随机函数族的任何实例都不能与真正的随机函数区分开，只要一个人不知道用于选择该实例的密钥即可。因此，根据定义，算法的选择或使用方式并不重要，只要它是安全的PRF：它们看起来都与不知道密钥的人相同。确实，已经有许多公开发布且可免费使用的PRF算法经受住了广泛的公众审查和密码分析，并且在全世界范围内得到普遍使用。由于未能发布自己的算法（或使用已发布的算法之一），Megamos加密芯片的制造商不仅违反了Kerckhoffs的原则，而且还使自己不受全球加密研究界的审查。 />综上所述，我很容易理解他们为什么会选择这样做：Megamos Crypto芯片被设计为嵌入到车钥匙中，随之而来的是存储容量和功耗方面的所有限制。在这样的小型低功耗设备上实现诸如AES之类的标准加密原语通常是一个挑战，在为此类设备专门设计的少数加密算法中，大多数是新的，但分析仍然很差，更不用说即使是已发布的设计也最终会导致速度与安全性之间值得权衡的问题。 Megamos Crypto的设计师可能一直希望，通过设计自己的算法并将其保密，可能无法轻易利用它的任何安全漏洞。
Ke，Kerchkhoffs的原则是重申自己的习惯：如果发现算法有收益，那么有人会这样做并从中获利。确实，根据法院的判决，在这种情况下，这似乎是很久以前的事情了，到2009年为止（当时该算法已包含在Tango Programmer工具中，由保加利亚一家公司以1000欧元的价格出售，并在法院判决中被描述为

顺便说一句，法院的判决甚至引用了编辑过的论文中一些有趣的部分，包括以下内容，这为发现的弱点的性质提供了一些线索。在Megamos算法中：

”“不幸的是，我们的第一次攻击很难缓解。阻止对手收集两条身份验证跟踪似乎是不可行的。此外，这种攻击还利用了密码设计过程中的弱点-例如内部状态的大小，需要对密码进行彻底的重新设计以解决这些弱点，为此，文献中已经提出了诸如谷物等轻量级密码，并且可以认为是合适的替代品Megamos加密货币。从积极的方面来说，我们的第一个攻击比第6节和第7节中的攻击在计算上更加密集，因此采取上述缓解措施以防止更为廉价的攻击非常重要。“在案文中，被告在他们的案件中（第19（xiv）段）还指出：

“基于Megamos Crypto算法的攻击仍然需要罪犯拥有汽车，以及钥匙，再加上两天的时间，就可以使用计算机程序来尝试很多可能性。“从措词和从Grain的建议来看，似乎“ Megamos算法”实际上可能是某种流密码。只要输入与密钥相结合，就可以认为流密码被视为具有任意长度输出的PRF，这确实是有道理的。流密码尽管作为密码构建块有其局限性，但仍作为低端系统的密码原语仍然非常流行。
基于比较密码输出的攻击，攻击本身似乎是一种相关密钥攻击。两个不同的随机随机数的密码（在身份验证过程中已知），并且大概包含内部密码状态的某种“已知暴力”枚举，以便恢复密码密钥的秘密（固定）部分。至少，根据法院的判决，情况就是这样。

#2 楼

从法院的判决中，我们发现研究人员实际上并没有对关键的应答器进行反向工程，而是一款名为“ Tango Programmer”的软件，它是用于制造应答器的第三方工具（软件和硬件）。 br />
Tango编程器很容易获得，但似乎需要与物理编程器一起购买。我强烈怀疑该软件是否会在文件共享站点上非法提供，或者如果您足够努力的话，甚至可能在制造商的站点上合法获得。

另一家Bicotech公司也生产类似的工具RwProg。该软件可从其网站下载。可执行文件已打包，但我敢肯定完全有可能对二进制文件进行逆向工程。

法院诉讼中还有其他花哨的信息，我建议您仔细阅读，更有趣的东西。他们非常强烈地鼓吹这种思想，即通过默默无闻的安全性是有效的。

#3 楼

“有人知道Megamos算法是什么吗？”

是的。根据http://www.bicotech.com/doc/megamos_cr.pdf（PDF）的说法（从我的角度提供了最好的描述），Megamos加密货币是： CRYPTO
读写高安全性设备-内存组织

说明

MC是一种高安全性的读写RFID发送应答器。在设备中实现了具有96位用户可配置密钥的质询和重新响应密码算法。

30位的可自由编程用户存储器和32位的唯一设备标识得以实现。魔术的特征。字1的位15和14用作锁定位。交付时，这两位的内容为“ 10”，这是写入和擦除存储器的要求。通过对电磁场的幅度进行调制来执行到收发器的数据传输。接收数据和命令的方式类似。

功能


片上加密算法（挑战和响应）


双向身份验证
EEPROM中96位的秘密密钥（不可读）
32位的固定设备标识
32位的用户存储器（UM）具有读取访问权限（OTP） ）
秘密可编程CID接口
锁定位以禁止编程
通过幅度调制执行数据传输
位周期=载波频率的32个周期

/>
您可能想阅读完整的PDF，因为我一直不遗余力地键入“内存组织”部分。






“是否有公开可用的算法规范，或实现该算法的任何公开可用代码？”

我不能给您直接指向包含加密货币规范的论文的链接，因为我敢肯定，一开始该论文不会为大众广泛使用。

但是，有些事情非常接近！

您应该阅读的相关出版物是：


http://www.bicotech.com/doc/megamos_cr.pdf

http://degate.org/documentation/diplomarbeit.pdf（德语）
https://www.usenix.org/sites/default/files/conference/protected-files/verdult_sec13_slides.pdf
http://www.isg.rhul.ac.uk/~kp/Carolina-Paterson-Megamos-comment-20130828.pdf
http://cybergibbons.com/reverse-engineering-2/reverse-engineering- megamos-crypto /



MEGAMOS的工作原理

为了解释加密的内部工作原理，让我简单地引用一下Cyber​​gibbons网站得到了很好的总结：Ilmari Karonen *的部分回答*显然，网络犯罪分子将引用的部分复制并粘贴到他的网站中，而没有适当地注明原始作者– Ilmari Karonen的回答，这导致我将错误的人归功于他。：


A汽车$ \ text {C} $和应答器$ \ text {T} $共享一个秘密密钥K。使用密钥K键入伪随机函数族$ \ text {PRF} $，即$ \ text {PRF} _K $。此PRF的输出分为F和G两部分。


$ \ rm C $选择一个随机数$ r $并计算$（F，G）= {\ sf PRF} _K（r）$。
$ {\ rm C \ to T：} \ r，F $
$ \ rm T $计算$（F'，G'）= {\ sf PRF } _K（r）$并中止，除非$ F = F'$。
$ {\ rm T \到C：} \ G'$
$ \ rm C $验证$ G = G' $。

此过程意味着应答器认为汽车知道钥匙和PRF，而汽车认为应答器知道钥匙和PRF。他们应该彼此进行身份验证。




实现它的代码

我不确定为什么会出现这个问题。我们拥有安全，快速且经过严格审查的强大加密货币。我不知道为什么要摆弄一个已知很弱的加密货币（如果没有破解的话）。目前至少知道3种攻击，并在我上面链接的出版物中进行了介绍。忽略了这样的事实：如果您发布算法，可能会遇到一些法律上的限制（我不是律师，所以我知道什么？），没有人阻止您获得所需的软件。只需将一些现金放在桌子上，然后尝试购买包括所需硬件的“ Tango编程器”，然后逆转算法…（在那儿，看到它，大声笑出来，然后在Megamos算法上关闭了机箱-从我的角度来看，那是浪费金钱。）