摘要我们提出了一种新的可信的否认设计来隐藏存储介质上加密数据的存在，这使得对手很难证明这种数据的存在。它可以被认为是加密和加密等工具的“精神继承者”，但有了极大的改进：它在Linux上本地工作，它支持任何选择的文件系统，并且可以管理每个设备的多个卷，因此使否认隐藏分区的存在非常可信。与基于ORAM的解决方案相比，舒莱克非常快、更简单，但不提供针对多快照对手的本地保护。然而，我们将讨论其架构有可能实现的安全扩展，并展示了为什么这些扩展可能足以阻止更强大的对手。我们将洗牌作为Linux的内核工具实现，添加了有用的特性，并对其性能进行了基准测试，显示与基本加密系统相比只有轻微的放缓。我们认为，对于那些言论自由受到镇压当局或危险罪犯威胁的人来说，舒夫莱卡克是一种
有用的工具
n. 目录；篇目
个人和敏感数据的隐私现在比以往任何时候都更是公众关注的一个重要话题。在当今这个紧密相连的世界里，数据通常在默认情况下被委托给在线第三方，数据保密性的最后一个堡垒是本地存储，因为物理断开大大有助于减少滥用访问的空间。然而，即使在那里，也需要实施一些保护措施，以防止可能缩小差距的对手。这样一个对手最微不足道的例子是小偷窃取用户的个人硬盘并读取其原始内容；这是一个非常简单和研究充分的威胁模型，其中存在许多健壮的磁盘加密解决方案。
然而，仅凭磁盘加密并不足以处理由压制性法律或其他不那么合法的方法（如“橡胶软管”）授权的对手。与前面的场景，这些对手获得超过简单的“离线”访问磁盘：他们在权力的位置，他们可以使用直接和积极地面对用户保护存储的内容，并通过（物理、法律、心理）胁迫，他们可以获得加密密钥任何加密内容可识别用户的设备。因此，在这个场景中，安全目标是仍然保持磁盘上一些选定的“关键”数据的保密，使这些数据甚至不可识别，从而允许用户编造一个关于存储内容的可信谎言。这正是可信否认（PD）的目标，这是一种强大的安全属性，使用户能够在过度或胁迫的对手检查的系统中隐藏敏感信息的存在
在安全存储的情况下，PD指的是用户即使在对物理设备的询问或法医检查中，也能合理地否认在设备上存储的某些数据的存在的能力。潜在的想法是，如果对手不能得出关于隐藏的敏感数据存在的任何结论，他们就没有动机进一步继续强制，因此（希望）限制了对用户的损害。PD在1998年[1]首次提出，从那时起，出现了许多不同的PD解决方案，试图平衡安全-效率的权衡。最流行的PD解决方案之一是TrueCrypt [46]，它于2004年首次发布，于2014年停产，取而代之的是其向后兼容和技术相似的继任者VeraCrypt [49]。
TrueCrypt和VeraCrypt仍然是最著名的PD磁盘加密工具，可能是因为周围的大型开源社区和良好的性能，但他们遭受许多缺点，未解决多年来，在安全和操作模型方面，如：只有一层额外的保密，有限的文件系统支持，和Linux有限的功能。在这项工作中，我们提出了Shufflecake，一种新的磁盘PD工具，旨在通过实现良好的安全性能权衡来解决这些和其他限制。
1.1尽管现有文献没有广泛报道，但不幸的是，强制性对抗性攻击代表了许多不同的现实情况。在这方面，大多数可证明的事实都涉及美国、法国或英国等国家的国家安全条款，这些条款允许检察官在法律上强制公民披露其加密存储设备[21,25,38,40,48]的密码，而不遵守这些行为将受到严厉的法律或经济惩罚。据报道，这些条款经常被滥用，有时甚至导致人们的合法隐私被[2,4,8,50]践踏。然而，来自西方国家的此类报告相对丰富，很可能是由于公众对政府运作的相对关注和关键的监督。在制衡体系不发达的国家，活动人士、记者、异见者和受压迫的少数民族的敏感数据受到侵犯的确切程度，只能通过一些偶尔成为国际头条[7,44]的少数零星案例来暗示。这些强制性的
1.2以前的工作提出了不同的存储方法，从选择干预的层开始。事实上，数字存储是由许多堆叠的层组成的，从最上面的“逻辑”层（文件系统）到更物理的层。这种分层结构使安全分析变得复杂，因为不同的PD解决方案关注不同的层，每一个层都导致不同的方法和优缺点。某些解决方案可以在文件系统层[28,35]上工作；它们必须实现一个丰富的接口，由复杂的面向文件和目录的方法（文件打开、文件读取、mkDir……）组成。其他方案选择在最低级别修改FTL[23]（ssd的闪存转换层），但这种方法显然导致了高度特定于供应商的解决方案。为特定层设计的解决方案的安全性可能会被能够访问较低层的对手击败。
一个健壮的PD解决方案的通用方法可以说是操作块层，即方案公开块设备接口（一个公共抽象层使用许多操作系统表示存储设备数组的固定大小的数据块），只提供一个bRead和bWrite方法。这是TrueCrypt等解决方案和舒夫莱卡克所使用的方法；在本工作的其余部分中，我们将只关注块层解决方案。在此框架中，单个底层磁盘或设备被格式化为承载一个或多个卷（逻辑存储单元，通常表示为虚拟块设备），每个卷都使用不同的（通常是密码派生的）对称密钥进行加密。当面对对手时，用户将密码提交给其中一些卷，称为诱饵卷（因为在某些情况下，它们可能包含看似无辜的数据）：PD安全保证，即使这些密码被放弃，对手对磁盘的检查仍然产生
没有任何线索暗示存在一些隐藏的卷。这些保证的正式定义背后的直觉是，对手无法区分所有密码已交出的情况和秘密信息的情况
安全模型。早期的PD文献主要集中在单个快照的对手上，他们被认为只检查存储设备一次。这被认为是一种自然的假设：在典型的情况下，活动家或记者在检查站被拦下或被逮捕并审问一次，她的电子产品被没收和分析。如果她成功逃脱，她将在未来的调查中保持高度警惕，特别是她将通过一些特定的程序（例如，通过重新格式化硬盘，或购买一个新设备）来更新使用中的PD保护。因此，在第二次检查的情况下，对手实际上将面临一个全新的PD存储实例，因此会回到单快照的情况。这是由TrueCrypt和VeraCrypt等解决方案所解决的威胁模型。
然而，随着时间的推移，单个快照威胁模型的安全性在文献中受到了质疑，不仅因为它依赖于良好的用户安全实践，还因为存储的技术发展带来了一个新的问题。在现代设备中，特别是固态磁盘（ssd）中，覆盖逻辑扇区通常会导致底层物理扇区被简单地标记为“未使用的”，而不是真正被覆盖，从而在之前的时间点留下数据内容的“痕迹”或“快照”。这反过来（理论上）可以让对手即使用一次检查也能打破合理的否认性，因为通过分析设备上留下的这些痕迹，我们可以看到某些位置的内容发生了变化；由于空的、未使用的空间不应该随着时间而改变，其中隐藏的信息可能会被泄露。这是在多快照安全模型中所考虑的场景。
有人可能会说，多快照攻击很可能非常复杂，以至于100%的隐藏卷存在的证据不太可能达到，而且在这个意义上的指控可能不会站在法庭上。事实上，我们并不知道在公共文献中没有一个案例因多快照攻击而被定罪。相反，在许多有记录在案的[36,37,47]案件中，即使是像真相[36,37,47]这样的简单系统也足以宣告嫌疑人无罪。这并不是说单快照和多快照的安全性是相等的：后者更强。然而，人们应该质疑，为了实现这种更强大的安全性，应该支付什么合理的价格（在性能等方面）。
ORAMs。多快照攻击是PD系统中一个众所周知的问题（TrueCrypt和衍生物在这个意义上也容易受到攻击），设计对策具有挑战性。到目前为止，只有少数结构[10]实现了多快照安全性，但性能成本很高，这使得它们对大多数用例都不实用。这些解决方案大多基于被遗忘的随机访问机器（ORAMs）。oram是一种加密方案，旨在隐藏受信任对象的访问模式（除了数据内容本身之外）
代理正在访问不受信任的存储器。自2014年以来，人们已经通过HiVE构建[6]研究了oram和PD之间的联系。简而言之，这个想法是，如果我们使用ORAM来访问一个设备，那么没有人，甚至是设备固件中的运行时后门，能够知道我们访问哪个（逻辑）位置以及如何访问，从而为实现PD提供了一个可靠的方法。然而，ORAMs非常慢：已知的[26]，任何大小为n的安全ORAM的带宽开销都是Ω（log (n)）。HiVE的论文通过以下观察结果规避了这个问题：如果我们不担心设备固件中的运行时后门，而只关心“传统的”多快照对手，即逮捕后调查设备物理层，那么我们不需要一个成熟的ORAM，因为读取操作不会改变设备的状态。因此，我们所需要的只是一个“只写”的ORAM（WoORAM），它只混淆写请求。其优点是，对于WoORAMs没有已知的效率限制，事实上，现有的WoORAM结构似乎比完整的ORAMs稍好一些。WoORAM方法引发了多方法的全新的研究方向
事实上，现有的WoORAM结构似乎比完整的ORAM稍微好一些。WoORAM方法引发了抗多快照PD解决方案[9,39]的全新研究，并且已经证明在一定假设下抵抗多快照安全性等同于使用WoORAM。
1.3现有解决方案的局限性到目前为止，可用的PD解决方案在可用性和安全性方面存在许多差距，这类解决方案的采用也暗示了这一事实。到目前为止，今天最广泛使用的是VeraCrypt，它有许多限制。基于wooram的技术在过去几年中被研究，作为解决traCrypt的安全问题的有前途的替代方案。然而，需要强调的是，即使是性能最好的基于wooram的方案也仍然非常缓慢或浪费。从这个角度来看： HiVE降低了大约200倍的I/O吞吐量，浪费了50%的磁盘空间，而一些最近的结构，如DetWoOram [39]，减缓了“只有”5倍，但代价是浪费了75%的磁盘空间。这给我们留下了一个困境，要么选择单快照、安全性有限的高效解决方案，要么选择具有不可接受的性能损失和更强安全性的WoORAM解决方案。
此外，WoORAMs的解决方案本身可能并不是防弹的。事实上，我们认为读取请求不改变物理设备的底层状态是一个很强的假设，并且很难用现代复杂的SSDs进行证明，例如，在固件的一些未文档内存区域中缓存读取请求，或将读取数据存储在临时缓冲区上以提高性能等。许多可信的否认解决方案（包括TrueCrypt）的另一个大问题是，当隐藏卷被解锁时，操作系统itelf（或安装在其中的其他应用程序）可能会无意中泄露隐藏数据给对手。这可能通过操作系统记录磁盘事件，搜索代理在解锁时索引文件，甚至像图像库或文档阅读器缓存预览等应用程序发生
打开的文件。以这样一种方式定制操作系统的行为来避免这些陷阱是[11]的一个几乎没有希望的任务。解决这个问题的一个解决方案是让操作系统本身包含在一个隐藏的卷中，这导致了TrueCrypt上“隐藏操作系统”的概念。然而，据我们所知，TrueCrypt（和VeraCrypt）仍然是这一想法的唯一实现，仅限于Windows操作系统。总的来说，我们可以说，一个能够平衡安全性和可用性的通用PD解决方案多年来已经严重缺失，特别是对于Linux，那里没有真正实际的解决方案存在。
1.4在这项工作中，我们提出了一种新的PD方案，该方案旨在在真相加密的效率和基于wooram的解决方案的安全性之间取得平衡。洗牌在块设备层操作，就像TrueCrypt一样，但有了重要的改进：1。它为每台设备提供了几乎无限数量的隐藏卷，并按分层排列：对于用户来说，解锁一个卷就足够了，所有“不太安全”的卷都将自动解锁。这改善了用户体验和操作安全性，正如我们将在第4.2节中看到的那样。 2.与TrueCrypt不同的是，它是与文件系统无关的，这意味着无论用户选择的文件系统如何，它的所有特性都是可用的。 3.它在Linux上本地工作，可以与内核集成，用于引导时和隐藏操作系统。 4.与基于wooram的解决方案不同，Shufflecake非常快（与裸的非pd系统相比，只能实现轻微的减速），浪费的磁盘空间不到1%。
此外，Shufflecake不仅实现了（可证明的）单快照安全性，而且还实现了在未来可能实现一种“可操作的”（即弱的）多快照安全性的特性。这些特性是舒弗莱卡克的分层设计和原子块再随机化，这在TrueCrypt等工具中是不可用的。我们将在第6节中讨论这个问题。我们用C语言实现了[45][45]，并在GNU通用公共许可证v2+下将其作为一个自由软件发布。
1.5感谢EPFL的爱德华·布格尼翁对舒弗莱卡克计划的支持和深刻的讨论，特别是关于碰撞一致性的话题。我们也非常感谢来自EPFL的维罗·埃斯特拉达-Gali˜nanes就卷腐败问题进行的深刻讨论。这项工作的一部分是由EPFL在EPFL M. Sc的背景下完成的。论文工作在库德尔斯基安全研究小组工作，在爱德华·布格尼翁的官方监督下进行，在T.G.的技术监督下进行。
在本节中，我们给出了将在本工作中使用的所需的准备。在下面，我们使用“iff”作为“当且仅当”。数组索引从1开始。通过（有效的）算法或程序，我们指的是族指数中深度和宽度多项式的统一电路族。我们隐式地假设所有算法都将族的索引作为第一个输入，因此我们经常会忽略这一点。在加密算法的情况下，我们称这种索引为安全参数，并用λ表示。我们经常会用反映其角色的名称来标记算法，例如。“对手”、“区分者”等等。如果算法A是确定性的，我们将输入x上的输出y表示为y ：= A (x)，如果它是随机的，我们使用y←A (x)；当剔除算法时，我们看在明确考虑内部随机r作为附加辅助输入时获得的确定性算法，我们写y ：= A（x；r）。我们将称一个可忽略的函数（用negl(x)表示），它比x中的任何逆多项式增长得都慢，并且超过一个为1减去一个可忽略的函数的函数。给定一个事件E，我们用¯E表示它的否定。芬兰
2.1密码原语我们假设熟悉基本密码结构，并建议读者，例如[24]进行更深入的研究。这里我们只是非正式地回顾一下最相关的概念。加密安全。我们通常会根据游戏或实验来定义加密方案Π的安全性，即捕获“打破方案的难度”，从而导致所谓的基于游戏的安全3。这通常需要比较对手A（建模为一种有效的算法）赢得一场游戏的概率，也就是说，打破方案，与“纯机会获胜”的基线概率，例如通过随机猜测。我们将这种概率的差异称为对手赢得Π游戏的优势，并且我们通过要求这个优势对于任何（有计算边界的）对手在λ中可以忽略不计，来定义（计算）安全性。
AdvGame Π (A) ：= Pr [A（Π，Game）→win]−Pr[猜测（Π，游戏）→win]≤negl。散列函数和kdf。哈希函数是一种算法，它将任意长度的字符串映射到固定长度的字符串中（例如，256位或512位）。在我们的例子中，哈希函数最相关的安全属性是抗碰撞性，这意味着在计算上很难找到映射到相同哈希值的两个不同的输入字符串。为了增加对预先计算的阻力3，存在其他框架，如基于模拟，但作为第一个近似，基于游戏的安全概念由于其直观和简单而非常方便。
攻击[32]，大多数哈希函数的实现使用一个额外的参数，称为salt（通常是一个非秘密的，每个96-256位的应用程序字符串），以进一步随机化它们的映射。用于加密使用的典型哈希算法是SHA256 [16]、SHA-3 [12]和BLAKE2 [42]。哈希函数被设计成在所需的计算资源方面是非常快速和高效的。当使用该函数来存储用户选择的密码的图像时，这实际上可能是一个不受欢迎的属性，因为它允许更快的对抗性暴力。在这些情况下，应该使用一个密钥派生函数（KDF）。kdf在功能上与哈希函数相似，但这种设计方式在广泛的计算设备上计算非常昂贵，例如不仅需要许多CPU周期，而且需要大量的内存和低延迟。用于密码学使用的典型kdf是Argon2id [5]和Scrypt [34]。
对称密钥加密和身份验证。关于加密，最基本的原语是对称密钥加密（SKE），也称为密钥加密。SKE方案是一对算法（一种用于加密，一种用于解密），它定义了字符串的域（明文空间）和共域（密文空间的子集)之间的双射。一个额外的输入，密钥，修复了所有可能的集合的双射，和SKE的正确性确保，如果使用相同的密钥，那么解密算法提供的反向的加密（非确定性解密的情况下具有压倒性的概率）。在许多实际应用程序中，一个典型的密钥的大小为128位或256位。这允许最多索引2128或2256个独特的双射，随着域空间变大，这通常比可能的双射数量要小得多。因此，由于这个原因，通常不可能要求覆盖所有可能的双射作为SKEs的安全属性。相反，安全性通常是根据不可区分的博弈给出的，具有re的强度
在这样的游戏中，对手的目标是区分她选择的两条信息的加密，给予额外访问加密加密（游戏中使用的相同的、未知的密钥）。该方案被称为IND-CPA安全，如果没有任何有效的对手A能够成功获胜的概率比随机猜测更好。请注意，这特别要求SKE必须是随机的，即，用相同的密钥加密两次相同的明文通常会产生两个不同的密文。我们将用密钥k（以及随机性r）对明文p（密文c）的加密（p、k、解密）表示为加密（解密（c、k、r))。随机r通常不需要随机r，所以在这种情况下我们将省略它。
如果除了隐私之外，还需要消息的真实性，那么ske就不够了，并且必须使用经过身份验证的加密（AE）方案来代替。声发射方案的工作方式与SKE类似，但要解密a
如果用于解密的密钥与用于加密原始明文的密钥不同，则给定的密文将失败。当这种情况发生时，我们编写解密过程返回⊥。这允许检查一个密文是否没有被一个恶意的对手更改或取代，从而授予消息的真实性和完整性。实现AE的一种典型方法是将消息认证码（MAC）附加到密文中。MAC是一个随机外观的位字符串，例如通过加密-MAC过程与密文和密钥组合上的哈希函数计算。除了其他属性外，mac非常有用，它可以检查所提供的密钥是否能够正确地解密密文（而不需要首先实际解密密文）。
阻止密码。块密码作为ske的构建块被广泛应用。这些算法通常提供两种不同的接口，一个用于加密，另一个用于解密。在加密模式下，它们以固定大小B（块大小）的明文块和K位加密密钥（密钥大小）作为输入，返回同样大小为B的密文块。如果使用相同的密钥，在解密模式下撤销此映射。换句话说，块密码实现了所有可能的（2B）空间的最多2K个大小的子集！B位字符串上的排列（及其逆）。最广泛使用的块密码之一是来自AES家族[20]的块密码，由AES-K识别（块大小为128位，密钥大小K为128、192或256位）。
为了将块密码转换为通用SKE，需要一种操作模式。这是一个确定性过程，描述如何将输入的任意长度的明文或密文分割成固定大小的块，并在这些块上迭代应用块密码。典型的操作模式是ECB、CBC和CTR [43]。在这些模式中，CTR通常因其更好的特性而被首选。为了实现随机化，作为对已知明文攻击的保护，许多操作模式还包括一个称为初始化向量（IV）的额外输入，通常是一个固定大小的字符串，如64、96或128位，不一定是秘密的，但根据消息是不可预测的和可变的。块密码也可以用于构建AE，但其操作模式与仅用于加密的操作模式不同，如GCM [29]。对于键大小为K的给定块密码B和给定的操作模式M，得到的SKE通常记为B-M-K，例如AES-CTR-192或AES-GCM-256。
2.2全磁盘加密全磁盘加密（FDE）是一种安全技术，通过使用“动态”加密来保护数字存储设备（如硬盘驱动器或SSD）的内容。这可以包括应用程序、用户文件，甚至是操作系统本身。FDE的主要目的是防止在发生设备盗窃、丢失或未经授权的物理访问时，未经授权地访问敏感信息。FDE的工作原理是使用密码（通常是块密码）来加密存储设备上静止的静止数据。用户（或设备制造商）必须首先通过提供加密密钥或密码来创建来初始化存储设备
并在设备上写入一个特殊的元数据结构，该结构表示一个使用所提供的密钥加密的（最初为空的）状态。为了防止空间分析的攻击，在初始化之前的第一步是用随机噪声完全覆盖设备。然后，每次系统通电或访问设备时，用户必须提供有效的密钥或密码短语来解密设备上的读写数据。此密钥不存储在设备上，每次设备准备使用（打开）时都必须输入，通常缓存在易失性和受保护的内存区域，从而在设备停止使用（关闭）或系统关闭时删除。除了一次性初始化阶段（根据设备大小的不同可能会很慢），加密过程通常对用户来说是不可见的，因为操作系统在数据读取或写入磁盘时处理数据的加密和解密。一旦提供了正确的密钥或密码短语，用户就可以正常地与设备交互，而无需手动加密或解密文件，因为操作系统只公开了对用户看起来未加密的虚拟化设备
FDE可以使用基于硬件或基于软件的解决方案来实现。基于硬件的FDE通常由专用的加密芯片来执行，而基于软件的FDE是使用在操作系统级别运行的加密软件来实现的。实现通常使用标准的块密码结构和操作模式来完成，如AES-CTR-256。一些基于软件的FDE解决方案的例子包括用于窗口的比特锁，用于macOS的FileVault 2和用于Linux [15,30]的LUKS。与非FDE系统相比，所有这些实现对性能的影响通常微不足道，这也要归功于广泛存在的专用CPU指令，以加快在智能手机和笔记本电脑等个人设备上的AES计算速度
请注意，如果整个操作系统通过基于软件的解决方案以这种方式得到保护，那么就会出现引导问题，因为操作系统本身不能在加密时本机运行。这可以通过拥有一个小的、未加密的引导加载程序来解决，它在操作系统的其他部分启动之前启动一个最小的FDE应用程序，或者使用通常通过硬件支持提供的底层解决方案，如可信任平台模块（TPM）。针对FDE的密码模式。对于磁盘加密中使用的块密码，[22]的XTS模式由于其性能和安全性而得到最广泛的采用。它通过从全局IV和扇区依赖的元数据中伪确定性地派生这些iv，避免了为磁盘上的每个块显式地编写iv的需要。以类似的方式使用CTR模式将是一个严重的安全错误，除非在每次写入数据时小心刷新（和存储）iv，这通常会对性能和空间使用产生影响。然而，后一种方法有一个潜在的优势：它提供了重新随机化块的可能性，即在不改变底层明文的情况下改变密文。
注意事项。需要注意的是，FDE主要是在静止状态下保护数据，这意味着当设备关机或处于锁定状态时，它最有效。它不提供保护，以防止未经授权的访问或数据泄露期间
系统正在运行，并已输入加密密钥或密码短语。特别是，FDE的有效性不如智能手机，这些设备的智能手机大部分时间都处于“打开”状态，而且不提供针对键盘记录器等恶意软件的保护，这些软件可能会拦截用户输入的密码，甚至直接访问未加密的内容。为了实现全面的安全性，FDE应该与其他安全措施相结合，如强身份验证、安全的引导进程和适当的访问控制策略。
2.3在本节中，我们提出了一个正式的基于游戏的PD安全定义。值得注意的是，该领域的几乎每一篇论文都给出了自己的安全定义，总是与其他论文略有不同；我们已经尝试将它们统一到一个单一的框架[10]中，但这里我们将遵循[6]中给出的更直观的方法，它非常适合我们工作的块层场景。在此设置下，用户使用PD方案将单个存储设备复用到ℓ独立的卷V1、V2、……Vℓ中，每个Vi与不同的密码Pi关联。PD方案支持每个设备的最大卷（因此1≤ℓ≤max)；最大值是公开已知的。卷和底层设备都是可进行块寻址的，这意味着它们所支持的读取和写操作具有块的粒度。方案Π的语义如下。定义1 (PD方案）。让ℓ≤max，和P1，……Pℓ用户提供的密码。PD方案Π是一个算法的元组：
Π。setup（P1，…，Pℓ）→Σ：初始化磁盘以托管ℓ卷V1，…Vℓ，用密码P1加密，…Pℓ；返回一个设备实例描述Σ，它封装了所有内容。–Π。读取（Σ，i，B）→d：从卷Vi中读取块地址B中的数据d（我们假设读取不修改实例）4。–Π。写入（Σ，i，B，d）→Σ‘：将数据d写入卷Vi的块地址B，并更新实例。以下正确性要求适用：对于任何固定的块B和卷Vi，如果Π.write（Σ，i，B，d）是查询Π之前最近的写查询。read（Σ‘，i，B），然后Π.read（Σ’，i，B）→d（为简单起见，我们考虑原子操作）。访问模式。让我们将一个访问定义为元组（op，=，=，d），op∈{读，写}（如果op =读，那么d是返回值），我是访问目标的卷的索引。让我们还将一个访问模式定义为一个（按时间顺序）有序的访问顺序，O =< o1，……，在>上。还定义了一个=⊥的空访问，实例Σ忽略。4注意，这也是基于wooram的结构，但不一定是基于ORAM或其他任意的PD方案结构。
PD安全PD安全博弈继承了IND-CPA博弈（选择明文攻击下的密文不可区分性）的密钥加密概念。对手是一个区分者，她面临的挑战是推断她是否与封装ℓ或ℓ−1卷的Σ交互。此外，她还可以选择要执行的读取或写操作，以捕获无论对卷执行的访问，不可区分性都必须保持的想法，因此包括对抗性的访问。游戏中的一个秘密位b决定了Σ0（包含ℓ卷）或Σ1（包含ℓ−1卷）是否首先在游戏中被实例化，并被用来与对手交互。在这两种情况下，我们都允许对手选择第一个ℓ−1密码5，而她的目标是猜测b。实验2（PD博弈，通用）对于PD方案Π和对手a，可信的否认性实验PD（Π，A）定义如下：
.A选择ℓ≤max和选择ℓ−1密码P1，……，Pℓ−1。 2.绘制了一个秘密的随机位b$←−{0,1}。如果b=为0，则采样一个额外的秘密高熵密码Pℓ$←−{0,1} λ，其中λ是安全参数6。 3.游戏创建了ℓ−b卷： Π.setup（P1，…，Pℓ−b）→Σb 4。A执行交互式查询。每个查询的工作原理如下： (a) A选择访问模式O0和O1，其中O0的意图是针对Σ0（因此可能包含Vℓ上的一些操作），而O1是针对Σ1（因此只包含V1上的操作，……，Vℓ−1）。她还选择了一点v，表示她是否希望在这轮融资结束时得到磁盘的快照。这些对抗性的选择受到限制，我们将在下一段讨论中讨论。(b)游戏只执行Ob（在Σb上，在步骤3中创建的唯一实例）。如果有请求，它会将生成的磁盘快照D发送给A。 5.在所有回合结束时，对手输出一点b‘。 6.游戏输出1iffb=b‘，否则输出0。
在这里，我们在选择访问模式时，和选择快照位v时，对手所受到的约束；我们现在将展示它们。如果没有任何这样的约束，我们将看到安全是不可能实现的；此外，精确的约束集将调节诱发的威胁模型。5这是对用户最不利的情况，因为我们认为这些密码已经被泄露了。6我们滥用表示法，将密码表示为二进制字符串，但是w.l.o.g.它相当于用户选择的密码与λ位熵的情况。我们假设用户至少会为隐藏的卷选择一个高熵的密码
对v位的约束。这个约束支配着对手的快照能力，从而支配着对手的能力。我们只定义了两个极端的情况：1。任意-无约束：允许对手在所有的交互回合中设置v = 1。这是最强的多快照安全的形式，因为对手可以在任何时候获得快照。 2.一次性的。对手是单快照，即只能为其中一个交互式回合设置v = 1
对访问模式的限制。这些约束定义对手的目标，通过指定两种情况她区分：如果PD方案是安全的（即对手无法区分）在游戏执行这样的约束，意味着用户，执行一些访问模式O0包括Vℓ操作，似乎可以声称执行相应的O1，只访问卷V1，……Vℓ−1（其密码已经交出）。关于约束条件的讨论。让我们首先澄清，为了在PD游戏中有希望，一些约束是必要的。否则，对手可以提交包含完全不同的O0和O1（逻辑）写访问，…，Vℓ−1，并且无法使这两种结果难以区分，因为对手持有这些卷的密码，所以它可以简单地验证两种模式中哪一种被执行。这表明需要一个最小规则，说明，无论执行O0还是O1，诱饵卷V1的结果逻辑内容，……，Vℓ−1必须是相同的。法国
写对诱饵卷V1的访问，…，Vℓ−1，并且没有办法使这两种结果无法区分，因为对手持有这些卷的密码，所以它可以简单地验证两种模式中哪一种被执行。这表明需要一个最小规则，说明，无论执行O0还是O1，诱饵卷V1的结果逻辑内容，……，Vℓ−1必须是相同的。从用户的角度来看，这个基本需求意味着我们不会试图将诱饵卷的写入伪装为其他东西，既因为我们不需要这样做，也因为即使我们想要也没有办法这样做
此外，我们注意到，许多PD解决方案（包括那些基于wooram的解决方案）以与读取请求完全不同的方式处理写请求，即，写请求可以触发某个卷扇区的分配或重组。这可能发生没有打破上面描述的最小规则：如果一个对手首先读取以前未分配的位置B，获得数据d，然后写相同的数据d在相同的位置B，这可能会导致状态的变化在实例没有改变其逻辑内容（由上面的最小规则）。这反过来又会使对手仅仅检查这种状态变化是否发生。然而，我们必须认为这种攻击微不足道：在诱饵卷上检测这种状态变化实际上不会危及安全性。因此，为了捕获这个概念，我们还要求写请求所触及的所有块集对于O0和O1都是相同的，对于所有卷V1，……Vℓ−1。我们强调，这种额外的约束也非常小，不会削弱实践中提供的安全保证；事实上，大多数方案要求更严格的约束，
单快照安全性在单快照的情况下，可以简化安全游戏。更正式地说，如果在第v位上强制执行“一次性”约束，那么实验2等同于同一游戏，即互动轮数设置为1，而不是被对手选择。这是因为在获取（仅）磁盘快照之前提交的访问模式可以全部连接成一个，因为它们不能自适应地选择；此外，获取快照后提交的所有访问模式都可以完全忽略，因为它们的影响不会被对手检测到。这个一轮游戏中的安全可以改写如下：定义3（单快照安全）PD方案Π是单快照（SS）安全iff为任何PPT对手A选择ℓ≤max，密码P1，…，Pℓ−1和访问模式O0和O1受2.3节概述的约束，它保持：
考虑到它与洗牌机比较的相关性，我们想在这里讨论TrueCrypt [46]，它是第一个提供PD功能的磁盘加密软件（现已停止）。它是在21世纪初开发的，在比特存储库[30]和LUKS [15]分别成为Windows和Linux上磁盘加密的默认标准之前。它的开发在2014年突然停止，但存在一个向后兼容的后继者（VeraCrypt [49]），它保留了大部分的设计原则，并在一些小方面进行了改进（比如更强的关键派生）。为了实现这项工作的目的，我们将只关注TrueCrypt，因为我们所有的考虑都同样适用于VeraCrypt。TrueCrypt可以以两种主要模式运行：使用“标准”（有时称为“外部”）加密卷，或使用“隐藏”卷。在前一种情况下，它在功能上类似于其他FDE解决方案，如LUKS（但使用随机外观的加密头）。在后一种情况下，一个隐藏的卷被嵌入到诱饵标准卷的内容所留下的未使用的空空间中。磁盘头和内容无法区分的事实提供了合理的否认
3.1设计truecrypt（像Shufflecake和许多其他现有的PD方案）可以作为堆叠驱动程序，即在另一个设备驱动程序上运行的设备驱动程序。它向上层公开了一个逻辑（虚拟）存储空间，从而指导逻辑转读和转写请求；然后，堆叠驱动程序执行其算法，将这些请求映射到物理块读和写请求，底层设备驱动程序管理物理存储空间。在这里，逻辑和物理之间的区别是在由堆叠驱动程序操作的转换之前和之后之间的区别，而不管物理存储空间是否也是一个虚拟设备。
TrueCrypt在设备内创建新卷时执行的第一个初始化操作是用随机字节填充磁盘，这对于包括LUKS在内的常规磁盘加密工具也是如此，正如我们已经讨论过的。磁盘的第一部分包含标准卷的固定大小的加密头，以及一个用随机字节填充的相同大小的空槽（从初始化过程中剩余）。然后是标准卷的实际加密数据部分，其中包括一些空空间，也填充了随机字节（来自初始化过程）。
TrueCrypt可选地允许“嵌入”到标准卷留下的（连续）空白空间中：这是提供可信否认性的机制。它的加密头放在标准卷的头之后的空槽中。标准卷和隐藏卷使用两个不同的密码进行加密。
TrueCrypt的一个大限制是，如果外部卷被格式化为FAT文件系统，它只能支持隐藏的卷。这是因为我们需要诱饵卷留下的空白空间是连续的。大多数现代文件系统（如ext4和NTFS）当它们在磁盘上写入数据时，它们会在磁盘上“来回跳转”，在中间留下许多空块或“洞”。相反，FAT文件系统是特殊的，因为它增量增长，直到删除文件创建的生理漏洞，占据所有的空间，直到它最后使用的块。这样，我们就可以让隐藏的卷在一定的偏移量处开始，在诱饵卷结束之后，然后线性地跟踪数据分配。TrueCrypt自动为隐藏卷计算一个方便的起始位置（在标准卷结束后留下一些遗留缓冲区），并将其放在隐藏卷标头的元数据中。虽然隐藏卷的逻辑大小遵循实际分配给它的物理空间，但标准卷没有调整大小，并保持逻辑地映射到整个磁盘。这是至关重要的，以不否认：如果我们调整标准vo
这种方法的另一个大的限制是，从一个隐藏的卷嵌入到一个标准卷，后者将非常有限的内容增长的可能性：隐藏的体积生活在标准体积的空白空间，这个看似空空间永远不会缩小（除了回旋余地缓冲区），或者隐藏的卷将被损坏。
3.2使用TrueCrypt的操作模型限制了用户可以做什么，以保持数据的完整性和合理的否认性。如前所述，一旦隐藏了隐藏卷，它的起始位置是最终的，它“冻结”诱饵标准卷的结束，限制它能够达到的最大大小。由于标准卷的大小不能调整适应隐藏卷，而是继续映射到整个磁盘，因此用户不能让它太过多并覆盖隐藏卷。这可以通过在标准卷中频繁地对FAT文件系统进行去碎片化，以及实际上不写入太多数据来实现。如果一个人想要绝对安全的数据损坏隐藏的卷，建议用户永远不要解锁日常使用的标准卷（除了胁迫），但总是解锁1)隐藏的卷，或2)隐藏和标准卷，但保持后者在只读模式。
标准卷必须包含“诱饵”数据，这将合理地说服对手，它是磁盘上唯一存在的卷。显然，用户只能在胁迫下将标准卷的密码移交给对手。这反过来又为隐藏的卷的损坏打开了大门。完全消除这种损坏风险是不可避免的，在TrueCrypt中，这只能通过频繁的备份来减轻。
3.3安全性在这里，我们分析了TrueCrypt在不同威胁模型下的安全性。伪随机性与LUKS和比特存储器等其他FDE解决方案不同，TrueCrypt格式的设备不包含任何明文报头。这意味着，当静止时，真实加密格式的设备与完全充满随机噪声的设备是无法区分的。这个特性是可取的在某些情况下，例如更直接，更少的风险如果一个人想嵌入TrueCrypt容器文件在另一个媒介使用隐写术，但代表一个权衡对易于集成系统的其他部分，这是首选的方法通用FDE解决方案如LUKS和比特柜。无论如何，必须强调的是，这个特性本身与PD无关，因为在PD场景中，对手总是提供至少一个解密密钥。
单快照安全。在TrueCrypt中，一旦用户提交了诱饵卷的密码并允许对手将其解密，唯一需要被对手“解释”的磁盘内容部分就是诱饵FAT文件系统结束后的未解密空间。然而，无论这个空间实际上是空的还是它包含一个隐藏的卷，它都将被仅用诱饵密码无法读取的随机字节填充。因此，即使存在一个隐藏的卷，用户也可以合理地声称剩余的空间是空的，并且充满了随机的字节：对手无法反驳这个错误的说法，甚至无法根据观察到的磁盘内容来质疑它的可能性。多快照安全。很容易看出为什么TrueCrypt在多快照威胁模型中是不安全的：如果对手在两个不同的时间点获得了磁盘的两个快照，并且用户同时已经对隐藏的卷进行了更改，会发生什么呢？通过比较这两个快照，对手清楚地看到，一些所谓的“空”块已经发生了变化，这立即揭示了第二卷的存在，因为TrueCrypt从来没有重新随机化
多快照安全。很容易看出为什么TrueCrypt在多快照威胁模型中是不安全的：如果对手在两个不同的时间点获得了磁盘的两个快照，并且用户同时已经对隐藏的卷进行了更改，会发生什么呢？通过比较这两个快照，对手清楚地看到一些所谓的“空”块已经发生了变化，这立即揭示了第二卷的存在，因为TrueCrypt从来没有重新随机化实际的自由空间。
TrueCrypt的隐藏的操作系统。TrueCrypt的最新版本提供了一个解决方案，解决操作系统通过“隐藏操作系统”功能泄露隐藏分区的存在。一个诱饵操作系统安装在一个标准卷中，而一个单独的操作系统安装在另一个分区的隐藏卷中。为了决定根据提供的密码启动哪个操作系统，计算机的引导加载程序被特别的TrueCrypt引导加载程序取代，该加载程序将首先尝试使用用户提供的密码引导诱饵操作系统，如果失败，将尝试启动隐藏的操作系统。由于诱饵操作系统本身永远看不到隐藏的分区，因此它甚至不可能意识到隐藏数据的存在。但是，请注意，此功能仅适用于Windows。
3.4其他限制在这里，我们讨论TrueCrypt的其他问题方面。值得注意的是，其中一些考虑适用于今天，但在21世纪初首次提出TrueCrypt时，就不那么相关了。首先，如前所述，如果需要一个隐藏的卷，则标准卷必须被格式化为一个FAT文件系统。然而，脂肪现在已经过时了：它曾经非常普遍，但现在几乎没有什么合理的理由再使用它了。因此，仅仅是我们使用脂肪这一事实就给对手发出了一个危险信号
另一个问题是，用户必须避免或限制诱饵分区的使用，以避免破坏隐藏的分区。然而，诱饵量(s)必须“看起来是合法的”：它必须是合理的，通过看他们的内容，他们是唯一的人。特别是，它们必须是合理的最新的：如果我们只研究隐藏的卷，并且完全忘记诱饵，解锁诱饵的对手会变得非常可疑，因为最近的更新是数月甚至几年。一般来说，隐藏自己并不在PD方案的范围内，即隐藏该方案正在被使用的事实。我们必须假设对手知道这个事实，例如，通过搜索用户的笔记本电脑，他们可以发现一个TrueCrypt安装。因为锁定TrueCrypt卷与随机数据，当要求第一个密码，我们甚至可以声称磁盘没有TrueCrypt格式，而是一个安全的擦拭过程的结果，甚至它是一个来自其他来源的随机数据。然而，一个现实世界的对手可以不相信，因为像Tr这样的系统
另一个很大的限制是，在每个标准卷中只支持一个隐藏的卷。这是一个问题，因为对手可能会合理地怀疑TrueCrypt正在通过其PD特性隐藏一些东西：如果我们只是打算加密一个卷，我们将合理地使用更广泛和支持的解决方案，如LUKS或BitLocker。用户可以声称，他们更喜欢使用独立的、利基的开源软件来保护他们的数据，这是相对可信的，但在设计PD方案时，最安全的做法是假设对手可能不相信这一说法，并要求提供第二个密码。这个问题的简短答案是：一个健壮的类似truecrypt的PD解决方案应该允许同时访问两层以上的卷。这样，我们可以创建一系列的卷越来越“私有”内容（很可能是诱饵），以揭示不止一个密码的对手，说服他们，基于结果解密内容，我们已经有效地放弃了我们隐藏，而事实上我们仍然持有密码一个绝密卷的存在他们没有m
4在本节中，我们介绍了我们的洗牌方案，我们解释了它的操作方式，并提供了一个安全分析。4.1根据设备的设计，我们指的是底层磁盘，它公开了一个物理存储空间。相反，卷是映射到设备上的逻辑存储单元。“洗牌”这个名字源于混合蛋糕片（设备），以提供许多隐私的堆积层（卷）。从概念上讲，舒弗莱卡克的操作包括四个功能：
.初始化一个设备：当一个新设备第一次准备好使用时，这只做一次。它包括用随机数据覆盖设备，要求用户提供所需的卷和相关密码的数字ℓ值，并使用这些信息创建一个带有元数据的加密头。在我们的实现中，此功能由init命令提供的。 2.实例化设备：这是准备洗牌初始化设备的初步阶段。它包括读取用户提供的密码，尝试用派生的密钥解密设备的报头元数据，如果成功，则恢复所提供的可用卷上的信息。在我们的实现中，这个功能对用户是不可见的（它与打开一起执行），因此我们不提供关联的命令。 3.打开卷：使用正确导出的卷键，从相关标头部分读取特定于卷的元数据。此元数据用于创建呈现给用户的逻辑设备，用户的操作系统可以向此逻辑卷发出SflcRead和SflcWrite请求。在我们的实现中，这个功能是可提供的
在其核心，洗牌是加密层上的一个块间接层。我们的间接层实现了一种机制，它已经是对TrueCrypt的一个强大的改进，因为它修复了两个关键的限制：它允许多个卷，并且它是独立于文件系统的。每个卷的数据解密密钥都是由密码和其他标头派生的随机性派生的。此外，卷ℓ>1的标头的解密有效负载还包含针对卷ℓ−1的标头解密密钥的副本。这允许通过使用单一密码递归地打开设备中存在的所有卷，这反过来提高了安全性和用户体验，我们将看到。
磁盘布局。设备的物理存储空间被静态地分为一个报头部分和一个数据部分。卷头部分位于磁盘的开头，它由固定大小的设备主块（DMB）和最大相同大小的卷头（每个都由卷主块（VMB）和位置图）组成，不管有多少有效的卷。这种轻微的空间浪费是必要的，以防止对手根据设备头的大小来推断卷的数量（即使不是所有的卷都被打开，通过分析数据分配模式，这可能是可能的）。让我们先分析一下所有这些部分，首先从数据开始。
数据部分。我们不像TrueCrypt那样，要求卷在物理上与磁盘上相邻，而是将它们作为加密（但未经过身份验证的）固定大小的切片，其中每个切片属于一个卷，并包含一定数量的块。第i个卷标头中的元数据允许通过将相应的切片映射为一个（虚拟的）连续空间来重构Vi的逻辑内容。
我们区分了大小为SL块的逻辑切片和大小为SP = SL +∆S的物理切片，其中∆S块用于存储该切片的加密iv。逻辑切片存储其各自卷的数据，而物理切片则用于在磁盘上保留空间，以分配加密的逻辑切片。物理切片可以不分配（即，任何卷都不声明），也可以映射到属于某个卷Vi的单个逻辑切片。在后一种情况下，从卷Vi的逻辑切片索引（LSI）σ到设备的物理切片索引（PSI）Ψ的映射是由一个函数GetSliceMap：（i，σ）7→Ψ，它是通过简单地查找一个位置图（基本上是一个每卷数组）来计算的。对卷Vi的逻辑块地址B的I/O操作可以通过SflcRead和SflcWrite这两个接口来执行。我们将在后面描述这两个接口，以及位置图的结构。
设备主块（DMB）DMB封装了所有与密码相关的数据。它以一个单一的KDF盐开始，为所有卷共享：这种盐通过KDF与卷Vi的密码结合，产生卷的密钥-加密-密钥（KEKi）。请注意，我们通过对所有最大体积使用一个全局盐来推导每个KEKi，否则每次我们实例化一个设备时，我们都会招致最大昂贵的不同键派生7。这并不妨碍安全性，因为密码散列从未存储在磁盘上，而只用于生成KEK，而KEK又被用作解密密钥。然后是最大DMB单元格，每个单元格都是经过验证的密文（连同相应的IV），用各自卷的KEK加密：明文本身是另一个加密密钥，加密卷的VMB（卷主密钥VMKi）。这种密钥解耦允许我们可能更改卷的密码，而不必使用不同的密钥重新加密卷的所有内容。对于粒度和一致性，DMB的总体大小被固定为恰好是一个块。其余的DMB单元格和未使用的DMB单元格都包含随机噪声。
卷主块（VMB）。第i个卷标头由卷主块（VMB）组成，后面是卷Vi的加密（但未经过身份验证的)位置图。我们将在下一段中讨论位置图。VMB是一个包含（未经身份验证的）密文的单个块，用卷主块的密钥VMKi和相关的IV加密。底层明文由以下字段组成：
卷的卷加密密钥（VEKi），用于加密实际数据部分和位置图。–上一个卷的VMB键VMKi−1（如果i为=1，则为随机值）。–设备中包含的切片编号。–直到填充块大小的剩余空间是随机的，但如果需要，可以选择用于嵌入其他与卷相关的元数据。
特定于设备的值NumSlices定义并修复了位置映射的大小，即使在设备大小被调整的情况下；它在所有卷头上复制，以便使用任何提供的密码进行解密。VMKi−1的存在允许我们对其他独立的卷施加一个层次结构（它们在数据部分都被平等地对待）。这样，一旦我们打开卷Vi，我们就可以迭代地遍由这个字段引起的向后链表，也可以打开卷Vi−1到V1。虽然这种方法损害了卷Vi“在中间”的否认性，但一旦提供了Vj，j > i的密码，它就不会损害安全游戏所定义的否认性：我们想要隐藏的卷是最后一个，Vℓ，而不是中间的。在第4.2节中讨论了这种方法的有效性。
切片地图。切片映射是数字切片元素的数组SliceMapi，其中每个元素都是一个PSI：每个元素的索引都是映射到该PSI的LSI映射。当卷被实例化时，每个卷的切片映射被解密并加载到内存中；当卷“活动”时，这些映射完全保存在RAM中，当卷关闭时保存在磁盘上（加密，连同它们的新iv）。切片映射存储在vmb之后，作为等大小的密文，大到足以处理所有可能的物理切片。RAM和磁盘空间要求是适度的：如果底层设备N块大，切片地图的大小只是ONP日志S N P，因为最多S N P物理切片，每个需要O日志S N P位索引。这反过来是由于选择在切片粒度上寻址存储空间，而不是块粒度，这将需要一个O（N log N）位的位置映射。
操作我们现在将更详细地描述舒弗莱卡克是如何运作的，并解释某些设计选择背后的基本原理。我们首先解释我们如何使用加密来保护磁盘上的数据。然后，我们查看磁盘上的物理数据分配和逻辑卷上的数据之间的间接层，即在物理切片和逻辑切片之间创建对应关系的机制。最后，我们将解释当数据写入逻辑卷时，需要新的逻辑切片时，这种对应关系是如何更新的。
加密层。在许多磁盘加密解决方案中，我们使用块粒度进行加密，这意味着块是I/O请求和加密/解密的单位；换句话说，一个IV对一个块进行加密。许多磁盘加密方案从一些公共上下文信息和卷的密钥（例如，这是在XTS操作模式下发生的情况）伪确定性地生成这些iv，以节省存储和检索它们所需的空间和I/O开销。对于FDE和单快照安全PD解决方案如TrueCrypt这样的FDE所覆盖的威胁模型来说，拥有这样一个确定性的程序来动态生成iv就足够了。
然而，在我们的例子中，我们坚持显式随机的IV，因为我们希望保持以一定程度的多快照安全性扩展Shufflecake的未来可能性，要求我们使用不同的IV重新加密一些块，同时保持它们的内容不变。因此，我们使用CTR模式，块的IV在该块的每次写入时刷新，以避免IV重用攻击。这意味着所有这些iv都存储在磁盘上。这种策略引入了一个潜在的性能问题：一个简单的实现将将每个逻辑SflcWrite转换为相应的物理数据块的物理写，以及整个相应的IV块的额外的读-更新-写。就I/O开销而言，这将是非常浪费的，因为我们只需要更新一个IV（例如，AES-CTR为16字节），但是我们被迫加载和存储整个块（通常是4096字节）。
我们通过在RAM中缓存IV块，在预定义深度(例如，1024个条目的LRU缓存中来避免这个问题。由于刚才讨论的性能原因，这个缓存不是通写的。通过这种方式，我们可能将同一IV块的许多更新（由许多逻辑Sflc写入触发，或由同一数据块的逻辑Sflc写入到同一数据块内的多个块触发）合并为一个物理bWrite，从而降低了I/O开销。对于每个物理切片，我们将其中包含的块的iv打包到切片开始时的∆S物理块中。在物理块和IV的磁盘上位置之间有一个简单的静态对应关系：物理切片中的（m个−∆S）块由初始∆S块中的第m个IV加密。因此，我们假设存在函数LoadIV和SampleAndStoreIV（具有自解释的行为），它们将一个物理地址Bphys作为输入，并返回相应的IV。类似地，我们认为加密功能（ptxt，key；IV）和Decrypt（ctxt，key；IV）根据隐含的操作模式对块起作用。
间接层。考虑对卷Vi的逻辑块地址B进行读取或写操作。这里有三种可能的情况：1。为卷i请求的操作（读取或写）发生在先前分配了逻辑地址B的块上。在这种情况下，我们需要有效地映射B到相应的物理地址Bphys。 2.它是一个B的SflcRead操作，它属于以前没有分配的片。在本例中，我们需要指定该行为。 3.它是一个B的SflcWrite操作，它属于以前没有分配的切片。我们需要定义如何分配一个新的物理切片。
请注意，切片内的块的偏移量由位置映射保持不变。因此，我们可以很容易地找到B所属的LSI σ，作为简单的σ：=B/SL。然后我们需要检查是否定义了GetSliceMap（i，σ）。幸运的是，正如我们在上面所看到的，位置图并不是太大。因此，在设备实例化期间解密位置映射时，我们可以将每个卷的这些位置映射的完整视图存储为由相关LSI索引的PSI数组，并为那些尚未分配的LSI定义一个特殊的返回符号⊥。然后让我们逐一分析上面的三个情况。在第一种情况下，我们只需要考虑刚刚获得的PSI Ψ，并添加一个正确的偏移量。这将给我们物理地址Bphys，我们将找到要解密的数据。从我们刚才讨论的，这可以作为Bphys ：= Ψ·SP+∆S+（BmodSL）。在第二种情况下，SflcRead应该返回一个默认的非错误值，例如，0。在这种情况下，对于卷的语义是必要的：虽然以前从未编写过错误，但块在逻辑上存在，但它在卷的逻辑边界内，所以返回错误是不正确的。注意我们如何
切片分配。只有当对属于一个新的、但未映射的切片的块的第一个请求到达时，才会延迟地创建切片映射。在这一点上，我们通过在自由片中均匀随机地采样一个物理片来创建这个片的映射：这保证了卷之间不会出现冲突，它们的片最终会在磁盘上随机交错。为了使这种延迟采样成为可能，我们需要有效地实现一个函数NewSlice：给定一个卷的标识符Vi和一个LSI σ，它为新切片返回一个相应的PSI Ψ。有不同的方法来实现这一点，这里我们使用表示切片的数组的排列来给出一个参考描述。具体地说，我们保留了一个内存中，每个设备的数组的ἧ大小为SNP（ἧ的最大可能数量），以及一个相同大小的位数组
bfld，一个“占用位场”，告诉我们哪些物理切片被占用了（psi是数组的索引）。最初，在设备实例化时，prm切片被初始化为prm切片[i]：=i，然后使用高效的渔民算法[13]进行排列。位字段bfld由所有自由元素初始化。当一个卷被打开，我们发现它映射到的物理切片时，我们将它们标记为bfld中的占用。然后，切片分配算法只是简单地反复从预打乱的psi数组中取下一个元素，直到位字段告诉我们它是自由的（在这一点上我们取它并将它标记为已占用）。保留一个有状态占用计数器octr以方便此任务，最初设置为1，然后增加为标记为自由的prm切片的第一个元素（即，prm切片的第一个octr元素保证在bfld中被占据）。这样，当需要一个新的切片时，就可以立即前进到下一个可用的切片。我们还需要在返回之前更新Vi的位置地图PosMapi（这是唯一一个最终会在磁盘上持续存在、加密的更改）。
索引的排列在每个设备实例化时都会发生变化，因此映射不是静态的。这些内存中支持的数据结构（数组和位域）的大小通常为OS N P log S N P，。延迟分配技术也允许我们过度提交总物理存储空间：我们可以让逻辑卷的大小总和超过总物理存储空间，只要“实际使用的”空间的总和不超过。但是，有意地限制这种过度承诺（对于打开的卷），以减少I/O错误的风险并改善用户体验。这可以使用VMB密文中的元数据字段来完成，如第6.5节所述。
卷操作。原则上，该方案中没有任何内容内在地阻止我们在任何时候自由、独立地创建、打开和关闭卷。然而，对于现实世界的操作，我们只提供一个密码（对于最秘密的卷），从而强制以分层的方式打开卷。要创建一个新卷，需要：新卷Vi的索引i、所选的密码和卷Vi−1的VMB键（如果i > 1）。通过这种方式，我们可以通过生成相关的键、填充VMKi−1字段、并将切片映射初始化为空来格式化报头。在数据部分上不需要进行任何操作。要打开一个卷，只需要它的密码来解密报头，然后允许加载其切片映射并解密其切片。为所提供的密码找到正确的头，只需尝试每一个密码，直到相关DMB单元格中经过身份验证的所有密码都被正确解密。关闭一个卷主要是通过删除相关的卷信息（并安全地删除其键）来修改RAM中的Shufflecake实例的状态。唯一需要的磁盘操作是那些需要持久化一些可能不同步的数据
不需要任何特定的操作来销毁一个卷，即将其从磁盘中移除。只要忘记密码，或者用随机字节覆盖头就足够了：根据PD保证，甚至没有办法证明该插槽中有一个卷，更不用说解密它了。4.2操作模型在本节中，我们定义了Shufflecake的操作模型，以提供一种安全的使用模式，允许用户保留合理的否认性和数据完整性。除了一些一般的约束外，我们还指定了用户在普通工作条件下必须做什么，以及他们在面对对手时必须如何行为。
数据损坏的风险。一个简单的观察显示，一个合法的使用模式实际上会带来很高的数据损坏风险。如果我们不打开所有的ℓ现有卷，而只打开我们计划使用的卷，我们就不会在RAM中加载所有的切片映射，这将导致对自由物理切片的完整设备的位场bfld的错误重构。属于仍然关闭的卷的物理切片将被视为空闲的，因此可能在数据写入期间被分配给打开的卷，然后这将覆盖它们的内容。这只能通过总是打开每个卷来确定地避免，无论我们将使用哪个卷：如果没有提供卷的密码，舒弗莱克没有办法检测它的存在。然后，由于物理存储空间的过度承诺，我们面临着为其他卷重新使用其物理切片的风险。然而，缓解措施确实需要是完美的。通过对未打开的卷使用某种形式的错误校正（从而牺牲一些空间），然后尝试恢复卷，当不打开所有卷可以减少损坏的风险
一般约束条件。当你初始化一个设备时，要做的第一件事是用随机字节完全填充它。尽管这个操作冗长而乏味，但即使对于单快照安全性也是至关重要的，我们将在第4.3节中看到，就像对于TrueCrypt一样。最敏感的数据应该放在足够高的体积中。当然，我们不能给出“使用至少3卷”或“6卷应该足够安全”的形式的精确指示，因为，根据克肖夫的原则，我们假设对手知道舒夫莱克，特别是阅读这份文件。将向对手披露的低阶量应该充满“轻度定罪”的数据，以便使攻击者相信有合理的理由隐藏它们。我们不指定更精确地什么样的内容会适合为此，部分原因相同（对手会立即标记为诱饵内容，并要求更多的密码），部分原因是它在很大程度上取决于上下文和对手具体是谁。诱饵卷也必须是“可信的”，特别是它们必须用r格式化
独自回家。在正常的操作条件下，当不面对对手时，用户建议的做法是解锁设备上存在的所有卷，以防止如前面所述的数据损坏。设计选择将卷链接到链接列表以帮助用户在这方面的原因是：这样，用户就可以通过向Vℓ提供密码来打开所有卷。在我们的实现中，这实际上是打开操作的强制语义：用户只提供他们想要打开的最后一个卷的密码，前面的卷会自动打开。其他实现当然可以自由地忽略卷头中的VMKi−1字段，如果知道所带来的风险，还可以给用户更大的灵活性。
在审讯中。当被对手询问并被迫泄露密码时，用户显然不能交出超过ℓ−1的密码（否则就没有什么需要保护的了）。虽然与该方案的密码安全性无关，但我们强调，为了使用户的谎言可信，他们必须在一定压力下或一段时间后泄露诱饵密码。请注意，负责任和安全的使用给用户带来了能够快速和可靠地回忆这些诱饵密码的负担，即使在痛苦中。这可能很难正确理解，因为用户在日常使用中推荐的行动过程是只打开最隐藏的卷。由用户定义使他们轻松完成此任务的最大卷数ℓ。Shufflecake实现可能包括附加功能来帮助用户在这个意义上，例如一个函数来检查诱饵卷的密码没有打开它，甚至一个谜题，与一些随机概率，提示用户也插入诱饵卷的密码时打开一个隐藏的。
安全消息。正如我们之前讨论过的，一个巨大的操作区别（还有其他解决方案，例如，嗨）和TrueCrypt是“对手不知道当她可以停止质疑你”，因为没有办法证明一个给定的密码解锁一个给定的设备上所有现有的卷（除非是密码解锁最大卷）。相反，在TrueCrypt中，要么只有一个规则的卷，要么是一个诱饵和一个隐藏的卷。在那些用户想要避免对某个对手显得不合作的情况下，这种区别可能很重要。在这种情况下，用户可能想要选择交出所有的卷，以及一种方法来说服对手没有其他卷存在，可能使用一个额外的“完全披露密码”，我们将称之为安全字。
实现这一点的一个简单方法，即使是在洗牌中，也是在初始化设备时实际创建所有最大卷。显然，记住最大密码对用户来说是相当麻烦的，所以解决方案是只记住ℓ+1密码：实际需要的ℓ卷的密码，以及最后一个最大卷的额外密码，这将是安全词。事实上，用户永远不需要打开超过ℓ卷的常规使用。在4.2节中讨论，这可能会损害的一致性，未打开的卷，但这并不重要：通过使用安全词，用户仍然能够说服对手，所有卷已经显示由于它们之间的链接和标题的密文身份验证。类似地，在像TrueCrypt这样的解决方案中，实现安全词的一个简单方法实际上总是创建一个隐藏的卷，即使只需要一个标准卷。
然而，我们强调，使用这个特性是一个危险的命题：如果存在这种可能性，并且用户可以这样做，那么为什么不这样做呢？对手可能会认为用户必须有一个安全词，并有披露该信息的压力。这将使那些决定不使用该功能的用户面临风险，然后他们可能会被强制采用该功能。这反过来又会破坏每个人的合理否认，因为现在我们有了一个系统，每个人都有一个安全的默认用词。我们认为，对于这个困境没有简单的解决方案：人们要么接受看起来不合作的风险，要么接受进一步的审讯，要么完全放弃PD。我们指出，据我们所知，安全字特性的问题（甚至只是它的可能性）可信的文件系统没有解决文献之前，所有实现我们知道（包括wooram的）采用某种形式的架构硬限制可能嵌套的保密级别。我们认为这是PD解决方案安全的一个严重的操作问题。出于这个原因，我们不仅不鼓励使用这个特性，而且我们还提出了一种方法来实现
4.3安全性在本节中，我们证明了Shufflecake实现了第2.3节中定义的单快照的安全性。定理4（软件的单快照安全性）。如第4.1节中所述的Shufflecake方案是根据定义3所述的单快照（SS）安全PD方案。的假设。在证明定理4时，我们将做出一些假设，以保持证明的紧凑和直观。我们假设w.l.o.g.所有的密码都被编码为长度为λ的位字符串。请注意，在整个第4.1节中，我们是如何避免给出具体的安全参数的。尽管在Shufflecake的真实实例化中，我们将拥有具有固定大小的输入和输出的加密原语（例如，128位iv，256位密钥等），但在这个证明的背景下，我们可以考虑它们的可变长度。这将允许我们产生一个渐近界，并像定义3中那样应用它，以证明任何（计算上有界的）对手的优势在安全参数中确实可以忽略不计。这样做，我们将处理加密货币
在洗牌设计中使用的是理想的选择。更具体地说：-KDF将被一个随机的预言OK所取代，将λ位密码和盐映射到真正随机的λ位字符串中。–对称加密方案将被一个理想的密码E所取代，将λ位密钥和iv映射到{0,1} λ上的真正随机排列。–DMB中使用的认证加密将被一对神谕取代神谕：神谕OAE，映射λ-bit密钥和IVs——纯文和密文空间之间的随机注入，和它的逆返回一个常数⊥失败符号如果查询以外的同域。所有这些神谕都将由游戏初始化
所有这些神谕将由游戏初始化，并提供给对手A以自由查询（以单一的时间代价）。提供的证明。让我们在第2.3节中解释的约束条件下考虑实验2，让D是游戏提供给对手A的“挑战磁盘快照”（即根据秘密位B的D0或D1）。对于给定的A，我们将考虑ℓ、诱饵密码P1、...，Pℓ−1以及访问模式O0和O1作为游戏实例的公共参数。首先让我们注意到，A在接收到挑战磁盘快照D之前执行的所有oracle查询都不能改变A的优势，因为它们与D（和秘密位b）完全不相关。因此，我们可以在分析中安全地忽略这些查询。然后，让我们定义Q为A在收到挑战D后对神谕发出的所有查询{qi}i的有序序列，并定义n ：= |Q|。还将Qi定义为查询序列（q1，…，qi）到查询qi。类似地，让我们将R定义为由返回的所有响应{ri}i的有序序列
神谕；也将Ri定义为在响应ri之前的响应序列（r1，…，ri）。我们认为执行的执行单查询状态的对手，状态只是前面查询的历史： A1 (D)→q1,2（D，Q1，R1）→q2，直到−1（D，Qn−1，Rn−1）→qn和（D，Qn，Rn）→b”。设KEKi、VMKi和VEKi分别为卷Vi的密钥加密密钥、VMB密钥和卷加密密钥。严格地说，在安全游戏中，值Pℓ、KEKℓ、VMKℓ和VEKℓ只在b = 0时进行采样。让我们考虑对它们进行采样，并在b = 1中没有使用。让我们用S表示元组（Pℓ，KEKℓ，VMKℓ，VEKℓ）∈{0,1} 4λ。让我们将事件Ei定义为Pℓ、KEKℓ、VMKℓ或VEKℓ出现在查询气中的事件（我们说查询气打击）。最后，让我们定义E：=E1∪…∪在至少有一个查询发生的事件中。我们将首先证明两个柠檬酱。引理5。Pr [E] = Pr [E | b = 0] = Pr [E | b = 1] = negl(λ).（对手只能以可以忽略的概率猜测Vℓ的一个秘密。）
证明。让我们证明S在统计上独立于任何查询qi∈∈。这个元组从{0,1} 4λ中均匀随机抽样，因此它的分布不依赖于公共值。由于神谕实现了理想的密码原语，因此它们的输出在统计上独立于输入；这不仅对单个输入输出对非常适用，而是联合存在的：任何输入的元组在统计上都独立于相应输出的元组（对于理想密码E，这只适用于关键输入）。特别是，S在统计上是独立于整个元组（D，R）的。由于Ai的输入，即元组（D，气−1，Ri−1）是（D，R）的一个（随机）函数，我们推断它的输出，即气，也必须独立于s。因此，由于（Pℓ，KEKℓ，VMKℓ，VEKℓ）是一致的，气包含，如Pℓ的概率是2−λ。因此，通过并界，Pr [Ei ]≤4·2−λ。再次使用并集界，我们得到：
这个表达式显然是negl(λ)，因为n在λ中最多必须是一个多项式。关于条件概率相等的最后主张是通过简单地观察到，这种推理无论b的值如何都成立。⊓⊔引理6。PrA(D)→1|b=0∧¯E=PrA(D)→1|b=1∧¯E.（除非她能猜出Vℓ的秘密，否则对手对b = 0和b=1中有完全相同的观点。）“证明”。这足以证明An的输入，即D、Qn和Rn，遵循相同的联合条件分布，无论是b = 0还是b = 1。
我们用归纳法证明了这一点。使用一个简明的符号，我们想证明以下数量不依赖于位b： Pr D，Qn，Rn |¯E，b=Prqn，Rn|D，Qn−1，Rn−1，¯E，b·Pr D，Qn−1，Rn−1|¯E，b表明第一个因素是独立于b将证明归纳步骤。为此，让我们进一步将其改写为：
公关qn|D，Qn−1，Rn−1，¯E，b·公关rn|qn，D，Qn−1，Rn−1，¯E，b第一个因素独立于b因为问是−1的输出，只需要D，问−1，Rn−1输入，所有这些都在条件。第二个因素与b无关，因为假定¯E成立，无论b = 0还是b = 1，神谕的行为都是相同的。这是因为在b = 0和b = 1的情况下，引人注目的查询是唯一可以触发不均匀分布的响应的ϗ输入。但是，如果我们通过以¯E为条件来排除这些查询，那么当b = 0时实例化的神谕与当b = 1时实例化的神谕完全可以互换。我们现在剩下证明诱导的基本步骤，对应于Pr D |¯E，b.让我们用贝叶斯定理将它重写为： Pr D |¯E，b= Pr¯E|D，b·Pr [D | b]
术语Pr¯E|b通过引理5与b无关。同样的Pr¯E|D，b：同样证明适用于引理5，因为推理是不变的当我们条件的概率实现d我们只需要证明公关[D | b]不依赖于位b，即磁盘快照遵循相同的先验（非条件）分布，无论是b = 0或b = 1。为了证明这一点，我们将使用舒弗莱卡克方案的实际性质。让我们继续逐个区域地分析磁盘布局。空格（空的DMB单元格、未映射的切片等）充满了均匀分布的均匀随机噪声。当b = 0时，卷Vℓ所占据的空间充满了对包含Vℓ秘密之一的查询的预言响应。这些响应是新的随机性，当b = 1时，它们与填充相同空间的噪声遵循相同的分布。我们只需要证明，当b = 0和b = 1时，诱饵卷的（解密）逻辑内容和元数据遵循相同的分布。事实上，在这两种情况下，卷的逻辑内容是固定的和相同的，由o0和O1决定(这是因为它们必须遵循constr
最后一步是表明，在b = 0和b = 1两种情况下，诱饵体积的位置图遵循相同的分布。通过第2.3节中定义的访问模式的第二个约束，我们得到，在这两种情况下，对诱饵卷的相同lsi触发切片分配。即使当b=为0时，对Vℓ的LSIs执行了更多的切片分配，这并不会影响分配给诱饵LSIs的PSIs上产生的可观测分布。这是因为切片分配总是在自由分配中随机地接受一个PSI，因此LSI被映射的顺序可以在不影响分布的情况下自由排列。因此，即使在b = 0的情况下，我们也可以等价地想象诱饵LSIs全部映射到Vℓ之前，产生与b = 1时相同的分布。这就是证明的结论了。⊓⊔证明（定理4的证明）。我们用公理5和6来证明A的优势，如定义3的公式1中所定义的，可以忽略不计。通过将方程1的两项条件条件为事件E和¯E，我们得到：
这就是证明的结论。⊓⊔5的实现和基准测试，我们用C语言实现了洗牌方案，作为Linux内核的一个基于设备映射器的开源驱动程序。我们在GPLv2+许可下发布了我们的代码。当前的版本是v0.4.1 [45]。本节描述了编程环境和我们实现的结构，并介绍了以其他流行的磁盘加密解决方案作为比较基准的具体性能指标。5.1实现的结构我们的实现由两个组件组成：一个dm-sflc内核模块（它完成大部分工作），和一个洗牌附带的用户域应用程序（用于正确管理卷）。内核模块是实际实现该方案的组件，它将逻辑请求转换为物理请求，并将切片映射持久化到各自的头文件中。密码学。加密原语由libg加密库[19]提供。我们的目标是128位的安全措施。我们使用Argon2id作为KDF，最近在Libgcrypt[18]中实现。我们使用AES-GCM-256作为一个经过身份验证的密码，而AES-CTR-256用于数据加密，wi我们使用AES-GCM-256作为经过身份验证的密码，而AES-CTR-256用于数据加密，使用128位iv。
美国的应用程序。此组件用于管理卷的创建、打开和关闭。为此，它可以管理每个卷标头的DMB和VMB。VEKi被传递给内核模块，以解密该卷的切片映射和数据部分，而VMKi−1被用于迭代地打开所有不那么秘密的卷，如第4.1节所述。这被卸载到用户区应用程序中，因为密钥管理在用户空间中处理得更好：例如，我们需要通过要求用户响应错误的密码来重试，而不是通过发出内核日志消息。将所有内容都委托给内核模块还有另一个技术障碍：像Argon2id [5]这样的最先进的kdf目前还没有在Linux内核加密API [31]中实现，而它们可以在像Libgcrypt [19]这样的用户空间软件库中使用。卷头的其他块包含用VEK加密的切片映射，由内核模块管理（在init时，当用户域工具编写空位置映射时除外）。
卷操作。洗牌init命令以一个设备路径作为输入，然后交互式地询问用户一个数字ℓ≤max和ℓ密码作为输入，正确格式化第一个ℓ卷头，并用随机字节填充剩余的max−ℓ插槽；这样，已存在的卷将通过删除它们的头（加密粉碎）来删除。除非提供了——跳过随机填充选项（例如，用于测试或调试目的），否则在格式化头部分之前，整个磁盘将用随机字节填充。此命令仅设置磁盘的格式：它不会创建与卷关联的Linux虚拟设备。洗牌打开命令将设备路径输入，要求用户一个密码，然后查找卷头，并打开所有卷的一个提供的密码，向后到第一个（走链使用VMKi−1字段VMB）。这是一个实际上创建表示卷的Liv/lenux虚拟设备的命令：这些名称是通过算法生成的。请注意，这些虚拟设备不是自动装入的，应该由用户装入和格式化它们
其他功能。除了标准特性如命令行使用帮助和打印在屏幕上的当前版本，我们的实现还提供了两个额外的功能：更改操作，允许用户更改卷的密码如5.1节所述，和一个测试操作，测试是否提供密码打开一定卷（和哪个）没有实际打开卷。这可能对希望定期召回密码到诱骗卷的谨慎用户有帮助，如第4.2节中所建议的。
5.2空间利用率一些因素影响Shufflecake的磁盘和RAM空间效率，即，存储的哪一部分包含来自上层的实际数据，哪些部分包含元数据，或者被浪费。总的来说，通过对参数的合理选择，以及对上层行为的合理假设，我们可以获得一个非常低的空间开销。对于我们的实现，我们将块的大小固定为4096个字节，以便更好地分摊由iv决定的每个块的空间开销。我们选择了SL = 256和max = 15。由于我们使用AES-CTR-256作为底层加密方案，所以我们需要16字节的iv。这导致了∆S=1的选择：一个单一的4-KiB IV块（包含256个IV）加密一个1-MiB切片。为了提供舒弗莱克空间利用的数值总结，我们观察到，在1 TiB磁盘的情况下，得到的理论最大可利用空间是1019.91 GiB，等于超过物理存储空间的99.6%的空间。
标题。使用上述参数，对于1-TiB磁盘，卷头的总大小约为N SP日志S N P，大约等于每个卷头4MiB：对于总设备头大小，约为60 MiB。静脉注射器。如前所述，我们将iv存储在磁盘上。通过我们实现的具体参数选择，我们有16字节的iv加密4096字节的块（256倍）；因此，我们只使用1 257（< 0.4%）的物理数据部分来存储iv。切片的内部碎片化。内部碎片化是空间分配中经常出现的问题，在文件系统理论中尤其广为人知和研究。出于性能原因，块层只处理块粒度；因此，文件系统必须分配一个整个块，即使它需要更少的空间，例如，托管一个文件。内部碎片化是由这种“过度分配”引起的问题。除此之外，Shufflecake通过其切片机制添加了另一层内部碎片：当一个卷请求一个块时，我们只为该卷保留一整个SL块的切片。此外，我们没有办法将这种过度分配通信到文件系统层，因此
、
幸运的是，一些文件系统确实表现出了这种行为。例如，常用的ext4文件系统定义了块组的概念，即由32768个连续块组成的组（对于4096字节的块，相当于128个MiB）。ext4的块分配器尽力将相关文件保存在同一块组中；具体来说，只要可能，它将目录的所有in节点存储在与目录相同的块组中；此外，它将文件的所有块与其inode [27]存储在相同的块组中。这个特性与我们选择的SL = 256的值很好：一个块组包含一个wh
切片的总数，因此从长远来看不会太碎片化。
释放未使用的切片。当相应逻辑片中的所有块都已被文件系统解分配时，我们的实现目前没有一种方法来回收已分配给某些卷但不再使用的物理片。我们将在第6.6节中讨论这个问题。然而，我们注意到，片的释放或多或少取决于正在使用的文件系统：具有良好连续性的文件系统往往会在数据移动或删除时释放连续的块（以及整个切片），而具有更高粒度的文件系统可能会更经常地“留下块”。我们不能释放一个切片，直到其中的所有物理块都被释放出来。因此，必须仔细评估任何切片释放机制的效率。
5.3基准测试：我们根据I/O性能和空间效率测试了我们的实现。测试环境是一个新安装的Ubuntu 23.04运行内核版本6.2.0，在笔记本电脑上配备了AMD锐龙7 PRO 6850U CPU，启用幽灵缓解，32gib4通道6400 MHz DDR5 RAM，和一个低功耗1 TiB NVMe微米MTFDKCD1T0TFK SSD。我们测试了洗牌机的切片碎片量（v0.4.1），其I/O性能，以及其他两个相关的磁盘加密工具的I/O性能进行比较： dm-crypt/LUKS（v6.2.0-26）和VeraCrypt（v1.25.9）。所有的测试都是在一个大小为8 GB的物理主SSD分区上依次执行的，使用ext4文件系统（这是与Shufflecake设想的最终用例最相关的一个文件系统）。在Shufflecake的情况下，我们用两个卷（一个诱饵和一个隐藏卷）启动分区，并对隐藏卷执行所有测试。类似地，在VeraCrypt的情况下，我们将分区格式化为一个标准的no-FS VeraCrypt卷，并在其中创建了一个6.5 GB的ext4卷。为了帮助实现可再现性，我们还在实现中包含了一套可执行的基准测试脚本
碎片为了评估碎片造成的片Shufflecake的分配，我们填满ext4文件系统增量大量的随机文件和目录饱和空间，在每一步我们测量空间的增加切片dm-sflc分配的隐藏卷和总量的数据写入。我们将空间效率定义为写入在磁盘上的真实数据与薄片分配的空间之间的比率（0 =坏，1=好）。结果如图7所示。正如我们所看到的，即使磁盘最初为空的，一些切片也会立即分配给ext4日志和元数据。然而，当数据被写入磁盘上时，碎片的影响很快消失：在数据容量的10%时，空间效率已经超过90%，在写入数据的25%时，空间效率达到95%。我们得出的结论是，Shufflecake的切片算法在我们模拟的随机使用模式中表现得很好，至少在ext4文件系统中，切片碎片可以忽略不计。
图7：当ext4文件系统填充时的洗牌空间效率。输入输出和带宽。为了测试洗牌软件针对dm-隐窝/LUKS和VeraCrypt的I/O性能，我们使用了fio基准测试工具，它可以灵活地测量各种指标。对于这三种磁盘加密工具中的每一种，我们都对文件系统上的大量数据执行了随机和顺序的读/写操作。我们为所有测试固定了相同的参数，例如包含32个操作的队列和包含4 kiB的块大小，这通常被建议用于评估磁盘的实际性能。在这些条件下，我们发现IOPs（每秒I/O操作）和带宽（以MB/s表示）之间的指标没有明显的差异，因此我们只报告查看带宽的结果。
表1：洗牌、dm-隐窝/LUKS和VeraCrypt（更高的=更好）的I/O性能（MB/s）。结果如表1所示。正如我们所看到的，与其他测试工具相比，舒弗莱卡克的I/O下降了约30%。我们相信这种开销在日常使用中是可以接受的。与WoORAMs的比较。与一些流行的基于ORAM的PD解决方案的比较，更令人信服地显示了舒弗莱克提供的实际效率优势。当然，必须强调的是，这些基于ORAM的解决方案旨在在一个比当前版本提供的单快照安全更严格的场景中实现PD。我们刚刚看到了如何实现了大约30%的I/O吞吐量，并使用了几乎所有可用空间。另一方面，HiVE [6]有一个很重的200x的I/O开销，并且浪费了50%的磁盘空间。DetWoOram [39]的读取开销为2.5倍，写取开销为10倍-14倍，并且浪费了75%的空间。
结论和未来的方向我们已经看到了洗牌如何代表一个可用的PD方案，比像TrueCrypt这样的解决方案具有许多操作优势。我们将它作为一个开源工具发布，希望在社区中建立信任和采用，并可能鼓励人们对未来的工作做出贡献。事实上，存在着许多进一步改进的可能性。我们将在本节中提到一些内容。6.1崩溃一致性到目前为止，达到成熟和采用日常使用的主要障碍是它没有崩溃一致性。这意味着，如果程序在一个或多个打开卷的操作期间崩溃，数据可能损坏，因为一些卷状态更改发生在-RAM中，并且在写入磁盘之前缓存一段时间。这对洗牌者来说是一个问题，因为如果将加密的数据写入磁盘和其相关的IV之间发生崩溃，加密将变得不可恢复。对于像LUKS或TrueCrypt这样的解决方案，情况有所不同，它们使用XTS的操作模式，因此对这个问题免疫，因为它们不使用显式随机的每块iv。解决这个问题，同时保持块随机化的属性，我们应该使个人逻辑写请求原子，也就是说我们应该掩盖这样一个事实，他们映射到几个物理请求（需要假定原子）：如果崩溃发生在两个物理请求，逻辑块的旧内容应该可以恢复，磁盘不应该处于“边缘”状态，不对应的任何逻辑骗局当在数据块更新和相应的IV块更新之间的时间窗口中发生崩溃时，Shufflecake会导致崩溃不一致。如前所述，Shufflecake对IV缓存采用刷新写入方法，而数据块立即写入磁盘，用新的IV加密（不会立即保存在磁盘上）；因此，当上层写入文件而尚未同步时，磁盘就处于“脆弱”（不一致倾向）状态：这是总操作时间的很大一部分。要解决这个问题，有必要进行IV缓存通写；目前还没有评估这种选择的性能影响，但它可能会很重。无论如何，这是不够的，因为它只会减少数据块更新和IV块更新之间的“漏洞窗口”，但它不会消除它。最终的解决方案是将每个IV块复制成一个长度为2的循环日志：IV块的更新同步先于数据块的更新，并覆盖两个版本中的旧版本；这样，如果崩溃发生在之后，和da无论如何，这是不够的，因为它只会减少数据块更新和IV块更新之间的“漏洞窗口”，但它不会消除它。最终的解决方案是将每个IV块复制成长度为2的循环日志：IV块的更新同步先于数据块的更新，并覆盖两个版本中的旧版本；这种方式，如果崩溃发生之后，数据块没有更新，它仍然是可解密的，因为相应的IV块没有被触摸。消除歧义（即，决定使用IV的两个版本中的哪一个）将基于数据块上的一个附加的MAC（与IV一起存储）；这只会是当卷打开后第一次读取块时，需要：之后，状态可以保持在RAM中（每个切片只有一个位）。另一种解决方案是将IV与数据块本身一起存储，以便将两个更新合并为一个物理请求，它浪费了更多的磁盘空间，但我们认为总体上是更好的。我们认为，除了减轻崩溃不一致的问题之外，这种方法可能会导致更好的I/O性能，因为在数据写入期间不需要单独的操作来写入IV块。至少在Linux系统上，磁盘存储空间的最小可寻址单位通常是512字节的扇区。因此，最少浪费的选择是将一个逻辑4096字节块（8个扇区，正如我们实现的情况）映射到9个连续的物理扇区：第一个包含IV，其他的那些则构成了数据块。这将导致磁盘空间的浪费（未用于上层数据的磁盘的比例）等于1 9 = 11.1%。由于IV只占用16个字节，第一个扇区的大部分将没有使用；我们可以使用剩余的空闲空间来包含额外的有用数据，例如一个MAC来检测IV的更改，以及一个“反向映射”，指示物理块对应的卷Vi的逻辑块B（这个信息当然会被加密）。此外，我们可以通过在第一个扇区有两个IV（每个都有对应的MAC），加上16个MAC，每个IV和8个数据扇区的每个一个，来构建一个更能适应故障的系统。这将允许我们使用扇区粒度来消除歧义，以防底层磁盘可以确保扇区写入的原子性，但不能确保写入几个相邻扇区的物理请求。6.2多快照安全的方式到目前为止，是完全容易受到多快照攻击完全相同的方式TrueCrypt（及其继任者，VeraCrypt）：当对手看到“空”片改变快照，唯一可能的解释是，仍然有一个隐藏的卷的密码没有提供。我们已经在第1.2节中讨论了为什么在实践中，这种安全级别的安全性在大多数情况下可能就足够了，以及为什么我们认为当前基于wooram的解决方案的安全性承诺基于难以证明的假设。我们已经知道[10]，实现“完整的”多快照安全性需要使用WoORAMs，这有严重的性能缺陷。无论如何，正如在第4节中提到的，我们在设计Shufflecake时希望能够添加可能有助于达到未经验证的、“操作”级别的多快照安全性的特性。在本节中，我们将探讨通过某个独立的、“正交”的模式模糊过程来实现这一目标的可能性，该过程独立于主方案运行，并且不干扰其单快照秒
安全概念重新审视。首先让我们澄清我们所说的“操作”多快照安全。的基本原理是，希望即使对手在多快照游戏的显著优势是可以忽略不计的（所以方案不是加密安全的严格意义上），它仍然足够低的调查在实践中不确定的对手。换句话说，我们认为，在这种情况下，法律或任何操作安全都与理论意义上的密码安全不同。
物理切片具有已知的边界，因此对手可以比较其基于切片的磁盘快照。这相当于检查每个物理切片跨快照所经过的后续更改或差异。回想一下，物理切片本质上是SP块的数组；当其中一个块发生变化时，可能是由于数据块的重新加密（有不同的IV，可能还有不同的内容），或者因为空块的重新随机化：加密方案的IND-CPA安全性保证了这两种情况的不可区分性。这意味着没有提示块的性质（即加密的块是数据还是空块）的历史记录泄露。因此，当比较一个物理切片的两个快照时，对手得到的唯一信息是哪些SP块发生了变化：它们是如何变化的是完全无关紧要的和没有信息的。换句话说，一个物理切片的两个快照之间的差异可以归结为SP位的位掩码，表示哪些块发生了变化，哪些块保持不变。
然后，对手的任务就是根据每个切片的不同序列来区分“数据切片”（即属于某个卷）和“自由切片”（没有映射到任何卷）。关键是，在解锁第一个ℓ−1卷之后，其余的空间可能包含也可能不包含另一个卷（在自由切片中可能有也可能没有更多的数据切片）：如果我们希望对手无法区分这两种情况，我们需要数据切片和自由切片的差异来看起来相同。一旦我们以这种方式框架问题，我们可以重新表述Shufflecake的弱点如下：自由片的差异位掩码总是全零，因此与数据片明显不同，数据片可能有一些位设置为1。然后，我们的任务是通过在自由切片中对一些选定的块重新随机创建一个非零差异位掩码，来“混淆”数据片（特别是属于Vℓ）中发生的变化。这样，用户就有希望能够声称，在“空”块上发生的所有更改都是由于这个混淆过程，而不是由于Vℓ的存在。没有版本
6.6回收未使用的切片目前，我们的Shufflecake实现没有回收不再使用的切片的机制：一旦一个切片被分配给某个卷，它将总是属于该卷，即使该卷的文件系统被清空了所有数据。最好实现一项操作，将空切片重新分配给免费可用的切片池，以便使跨卷的空间分配更有效，并限制过度承诺的风险。显然，我们需要从上层的某种提示来触发这个操作。为此，我们需要拦截文件系统发出的修剪请求。这些命令实际上是除了读写之外硬盘接受的第三条指令；它们是文件系统向磁盘指示某些扇区不再包含用户数据的一种方式，因此内部磁盘控制器在重组自己的内部间接层[17]时可以避免复制它们。这些命令对于磁盘虚拟化系统的效率也至关重要，例如Shufflecake，这些系统会提交总底层空间，因此需要利用每个机会进行操作
一旦我们有了这个机制，我们就可以设计一种方法，将新释放的物理切片重新分配到随机位置的可用切片池中，这样当需要新切片时，NewSlice（算法3）将以均匀随机概率返回它。更具体地说：假设舒弗莱克拦截了一个操作系统信号，告诉我们在LSI σ上的卷Vi的逻辑切片现在是自由的。我们定义了一个函数回收切片（算法4），它可以在NewSlice使用的相同结构上运行，也可以在感兴趣的卷的位置图上运行。该函数清除回收切片的占用位场和位置映射中的条目，然后通过执行另一个Fisher-Yates迭代，将PSI移动到prm切片的随机位置（在octr之后）。我们使用一个子函数反向洗牌，作为输入PSI，返回找到该PSI的prm切片索引，如果不存在则返回错误。实现这个子函数的方法可以有所不同，例如，通过在内存中保留打印片的反向映射，或者每次都进行线性搜索。
6.7无限卷数洗牌机假定任何设备都可以提供的最大可能卷数。即使这个限制可以通过实现自由选择，也希望有一种方法来为每个设备创建无限数量的卷（取决于空间可用性）。这不仅将消除对该方案的人为限制，而且还将无法实现任何一种类似安全词的技术（如第4.2节所述），从而加强其操作安全性。
显然，为了实现这一点，卷头不能在磁盘的开始处相邻和打包。进一步调查的一个想法是嵌入每个头（除了第一个，“少秘密”，仍将在开始）在设备内的随机位置，并让他们通过前面的卷头通过一个特别的指针字段总是存在，和区分与随机没有正确的密码。然而，遍历这个链接标题列表会存在一些挑战。特别是，当用户在卷实例化时提供一个密码时，我们如何知道密码是否错误？如果没有，我们如何到达通过密码解锁的正确的头？有可能为设备上任意数量的“假”头设计一些复杂的连接方案，但在任何情况下，以下限制将适用
首先，虚假的头不能“保留”磁盘的一个区域，否则我们会浪费太多的空间。在设备初始化过程中，它们可以被放置在任何位置，但是当一个新的切片分配落在它们的位置时，应该释放该空间。可以想到不同的方法来处理这个，例如通过动态移动假头到另一个自由位置如果他们即将被覆盖，或简单地接受打破列表的风险随机点使用（因为这不会影响一致性的“真正的”卷，它仍然足以证明先验的不可能生成安全词）。在任何情况下，除了保留分配的差异，“假”和“真实”头应该平等对待，或采取额外的预防措施来维持PD。
其次，一旦用户插入密码来实例化设备，我们可能就无法再判断密码是解锁了什么还是错误的（例如，打字错误）。相反，根据选择的解决方案，程序可能会继续遍历链接列表寻找解密密码，直到它找到正确的标题，或列表破碎（例如，一个虚假的头被覆盖），在这种情况下，我们可以说密码是错误的。我们甚至可以设想，用户应该手动终止一段时间后提供的密码不成功，因为实现中的任何硬编码超时都可能通过插入可能的头数的人为限制来取消这个功能。实现这个想法的一种可能的方法可能是：1。将DMB和VMBs合并成统一的、每卷的标头。 2.每个标题都是一个较大的切片。 3.每个标头还包含一个具有随机值nxtptr的字段。
4.除了第一个之外，头位于随机磁盘位置，这是前一个头的nxtptr的一个（公共）函数。 5.在init期间，如果发生碰撞在nxtptr生成的位置上另一个已存在的头，当前生成的nxtptr值被丢弃并再次采样，直到发现一个合适的强迫（因为总头大小应该可以忽略不计与设备大小相比，这应该是非常有效的）。 6.所有的标头在功能上都是等价的，并且包含相同的字段。 7.第一个头包含一个KDF盐的值，而其他头中的相同字段要么未使用，要么使用（快速）哈希函数为每个头重新盐密码派生的键。 8.舒弗莱卡克将以通常的方式为卷分配切片
只是考虑到头位置的切片被永久占用。上面的想法可能非常有效，但它仍然需要指定一种有效的方法来嵌入这种方式的位置映射，它可能大于一个切片。这里有许多选项可以评估，从头开始的链接列表，到多个分支指针。可能还有其他好的方法来实现几乎无限数量的可能性，我们将其留给未来的探索。
6.8如第1.3节所述，仅提供数据存储量的PD解决方案，由于操作系统和其中安装的其他应用程序的泄漏，将永远不会达到令人满意的操作安全水平。为了解决这个问题，操作系统本身在一个隐藏的卷中运行是很重要的，就像它是使用TrueCrypt的隐藏操作系统概念来完成的那样。洗牌的自然演变将在启动时启动（例如，作为一个GRUB模块[3]），并启动安装在一个卷内的整个Linux发行版。或者，还可以部署一个特别的、最小的洗牌引导加载程序。
更具体地说，最终可以成为一个完整的以pd为重点的Linux发行版，在安装过程中，用户在引导中创建卷和安装其他发行版。为了提高操作效率和安全性，第k层的每个操作系统都应该知道第j < k层卷中的文件系统和操作系统（这是由<卷之间的层次结构实现的）。这也将允许管家守护进程从当前运行的操作系统运行，并在低层次操作系统的后台操作，例如通过执行系统更新，下载电子邮件等，以便所有这些诱饵系统保持最新，即使用户忽略了定期使用它们。这反过来又可以减轻人们在交出诱骗密码时对对手的怀疑。作为为每个卷提供完整Linux发行版的替代方案，可以使用像Qubes OS [41]这样的基于管理程序的解决方案。然而，为了验证这种方法，需要进一步的分析，以确保管理程序（没有考虑PD设计）不会泄露隐藏卷的存在
引用1。安德森，李约瑟，沙米尔，A.：隐写文件系统。见：计算机科学课堂讲稿（01 2000）。https://doi.org/10.1007/3-540 -49380-8_6 2.揭露：英国地方议会利用里帕秘密监视公众。[在线；https://www.theguardian.com/world/2016/dec/25/britis h-councils-used-investigatory-powers-ripa-to-secretly-spy-on-public（2016）3。Y.： GRUB引导加载程序。动手启动：学习Linux、Windows和Unix pp的引导过程。133–181 (2020) 4.BBC：一名男子因拒绝使用电脑密码而入狱。[在线；访问2023-10-04] https://www.bbc.com/news/uk-england-11479831（2010）5。阿贡2。[在线；https://www.password-has hing.net/#argon2（2013）6。布拉斯，E.O.，梅贝里，T.，努比尔，G.，奥纳里奥格鲁，K.：使用只写的强大的隐藏卷。见：2014年ACM SIGSAC计算机和通信安全会议论文集。p. 203–214.中国化学会‘14，计算机协会，纽约，纽约，美国（2014）。https: //doi.org/10.1145/2660267.2660313，https://doi.or
卡西亚尼岛， D.: 为什么笼子主任扣留密码。[在线；访问2023-10-04] https://www.bbc.com/news/uk-41394156（2017）9。查克拉博尔蒂， A., R.：读优化顺序只写无关的RAM。隐私增强技术进展2020,2,216-234（2017），https://api.semanticscholar.org/CorpusID：201070384 10. Chen， C., 梁，十世，预言家， B., 似乎可以否认的存储。隐私增强技术论文集2022,132-151（04 2022）。https: //doi.org/10.2478/popets-2022-0039 11. Czeskis， A., 希莱尔D.J.S.，科舍尔，K.，格里布尔，S.D.，科诺，T.，施奈尔， B.: 击败加密和可否认的文件系统： TrueCrypt v5. 1a和争论的操作系统和应用程序的情况。详见： USENIX安全热点话题峰会（HotSec）（2008）12。Dworkin，M.： SHA-3标准：基于排列的散列和可扩展输出函数（2015-08-04 2015）。https://doi.org/https://doi.org/10.6028/NIST .联邦信息处理标准202 13.费舍尔-耶茨的洗牌。正式证明存档（2016年9月），http s：//isa-afp.org/entries/Fisher_Yates.html，正式证明开发14。Estra
16.弗兰克尔：使用HMAC-SHA-256，HMAC-SHA-384，和HMACSHA-512与IPsec。RFC4868（2007年5月）。https://doi.org/10.17487/RFC4868, https://www.rfc-editor.org/info/rfc4868 17.作者，K.：NAND-Flashssd中TRIM命令的数学模型。见：第50届东南地区年度会议论文集。p. 59–64.ACM-SE ‘12，计算机协会，纽约，纽约，美国（2012）。https://doi.org/10.1145/2184512.2184527, https://doi.org/10.1145/2184512.2184527 18.GNU项目： Libgcrypt 1.10.1已发布。[在线；访问2023-10-04]https://<ϟ5>-gnu/2022-03/msg00007.html（2022）19。GNU项目： Libgcrypt。[在线；https://gnupg.org/soft ware/libgcrypt/index.html（2023）20。高级加密标准（AES）。网络安全2009（12），8-12（2009）。https://doi.org/https://doi.org/10.1016/S1353-4858(10)70006 -4 21.在维基百科中，免费的百科全书。[在线；访问2023-10-04] https://en.wikipedia.org/wiki/In_re_Boucher（2022）22。Ele研究所
问：是的，有一个模糊的内存下界！见：沙查姆，H.，博尔迪雷瓦， A. (密码学的进展-密码学2018。页523-542。施普林格国际出版（2018）27。Linux： ext4高级设计。[在线；访问2023-10-04] https://docs.ker nel.org/filesystems/ext4/overview.html（2022）28。麦当劳，StegFS：一个用于Linux的隐写文件系统。见：信息隐藏问题国际研讨会。pp.463–477.施普林格（1999）29岁。伽罗瓦/计数器操作模式（GCM）。提交给NIST操作流程模式20,0278-0070（2004）30。微软：比特锁。[在线；https://docs.microsoft.com /en-us/windows/security/information-protection/bitlocker/bitlocker-o透视图（2022）31。内核加密API。[在线；访问2023-10-04] https://www.kern el.org/doc/html/v4.16/crypto/index.html（2022）32。做一个更快的密码分析时间-记忆的权衡。在： Boneh，D。(ed.)秘密成员《计算机科学课堂讲稿》，第2729卷，页。617–630.施普林格（2003年），http://dblp.uni-trier.de/db/conf
- 帕特森取自父名 D., Katz：廉价磁盘（RAID）。ACM SIGMOD记录17（07 1988）。https://doi.org/10.1145/ 50202.50214 34。珀西瓦尔， C., 基于扫描密码的密钥推导函数。RFC7914（2016年8月）。https://doi.org/10.17487/RFC7914, https://www.rf c-editor.org/info/rfc7914 35.z：缺陷：一个可否认的，用于对数结构化存储的加密文件系统。见：网络和分布式系统安全研讨会（01 2015）。https://doi.org/10.14722/ndss.2015.23078 36.巴西银行家的加密货币让联邦调查局感到困惑。[在线；访问2023-10-04] https://www.theregister.com/2010/06/28/brazil_banker_crypto_lock_out/（2010）37。路透社：英国要求《纽约时报销毁斯诺登的材料。[在线；访问2023-10-04] https://www.reuters.com/article/us-usa-security-snowden-nyt网站-idUSBRE97T0RC20130830（2013）38。RIPA：2000年调查权力的监管法案-维基百科，免费的百科全书。[在线；https://en.wikipedia.org/wiki/Regu lation_of_Investigatory_Powers_Act_2000（2022）3
R.： Qubes操作系统架构。无形的东西实验室技术代表54,65（2010）42。萨里宁，M.J.O.，奥马森，j.p.：BLAKE2密码散列和消息认证代码（MAC）。RFC7693（2015年11月）。https://doi.org/10.17487 /RFC7693, https://www.rfc-editor.org/info/rfc7693 43.NIST块密码操作模式。密码学34(2)，163-175（2010）44。一个叙利亚难民是如何冒着生命危险亲眼目睹暴行的。[在线；https://www.thestar.com/news/world/2012/03/14/how_ a_syrian_refugee_risked_his_life_to_bear_witness_to_atrocities.html（2012）45。洗牌项目：洗牌网站。[在线；访问2023-10-04] https://shufflecake.net（2022）46。TrueCrypt基金会：真相加密的主页。[在线；访问2023-10-04] https://www.truecrypt71a.com/（2015）47。美国上诉法院，第十一巡回上诉法院：美国诉。约翰·能源部，没有。11-12268和11-15421-华盛顿特区摘要No.3：11-mc-00041-MCR-CJK。[在线；访问2023-10-04] https://caselaw.fi ndlaw.com/court/us-11th-circuit/1595
