open-courses
  • 公开课笔记
  • CMU 15-445/645 Database Systems
    • Relational Data Model
    • Advanced SQL
    • Database Storage
    • Buffer Pools
    • Hash Tables
    • Tree Indexes
    • Index Concurrency Control
    • Query Processing
    • Sorting&Aggregations
    • Join Algorithms
    • Query Optimization
    • Parallel Execution
    • Embedded Database Logic
    • Concurrency Control Theory
    • Two Phase Locking
    • Timestamp Ordering Concurrency Control
    • Multi-Version Concurrency Control
    • Logging Schemes
    • Database Recovery
    • Introduction to Distributed Databases
    • Distributed OLTP Databases
    • Distributed OLAP Databases
  • UCB - CS162
    • OS intro
    • Introduction to the Process
    • Processes, Fork, I/O, Files
    • I/O Continued, Sockets, Networking
    • Concurrency: Processes & Threads
    • Cooperating Threads, Synchronization
    • Semaphores, Condition Variables, Readers/Writers
    • Scheduling
    • Resource Contention & Deadlock
    • Address Translation, Caching
    • File System (18,19,20)
    • Distributed Systems, Networking, TCP/IP, RPC (21,22)
    • Distributed Storage, Key-Value Stores, Security (23)
    • Security & Cloud Computing (24)
    • Topic: Ensuring Data Reaches Disk
  • MIT - 6.006
    • Sequence and Set Interface
    • Data Structure for Dynamic Sequence Interface
    • Computation Complexity
    • Algorithms and Computation
    • Structure Of Computation
    • Graph & Search
    • Tree & Search
    • Weighted Shortest Paths
    • String Matching, Karp-Rabin
    • Priority Queue Interface & Implementation
    • Dictionary Problem & Implementation
    • Sorting
    • Dynamic Programming
    • Backtracking
    • Self-Balancing Tree
  • MIT - 6.824
    • 2PC & 3PC
    • Introduction and MapReduce
    • RPC and Threads
    • Primary/Backup Replication
    • Lab: Primary/Backup Key/Value Service
    • Google File System (GFS)
    • Raft
    • Lab: Raft - Leader Election
    • Lab: Raft - Log Replication
  • Stanford-CS107
    • 原始数据类型及相互转化
    • 指鹿为马
    • 泛型函数
    • 泛型栈
    • 运行时内存结构
    • 从 C 到汇编
    • 函数的活动记录
    • C 与 C++ 代码生成
    • 编译的预处理过程
    • 编译的链接过程
    • 函数的活动记录续、并发
    • 从顺序到并发和并行
    • 信号量与多线程 1
    • 信号量与多线程 2
    • 复杂多线程问题
    • 函数式编程 - Scheme 1
    • 函数式编程 - Scheme 2
    • 函数式编程 - Scheme 3
    • 函数式编程 - Scheme 4
    • 函数式编程 - Scheme 5
    • Python 基础
  • MIT - 6.001 - SICP
    • 什么是程序
    • 程序抽象
    • 替代模型
    • 时间/空间复杂度
    • 数据抽象
    • 高阶函数
    • Symbol
    • 数据驱动编程与防御式编程
    • 数据抽象中的效率与可读性
    • 数据修改
    • 环境模型
    • 面向对象-消息传递
    • 面向对象 - Scheme 实现
    • 构建 Scheme 解释器
    • Eval-Apply Loop
    • Normal Order (Lazy) Evaluation
    • 通用机
    • 寄存器机器
    • 子程序、栈与递归
    • 在寄存器机器中执行
    • 内存管理
  • MIT - 6.046
    • Randomized Algorithms
    • Skip Lists
  • System Design
    • Twitter
    • Cache Consistency & Coherence
  • DDIA 笔记
    • Replication
    • Transactions
    • The Trouble with Distributed Systems
    • Consistency & Consensus
  • Papers We Love
    • Consistent Hashing and Random Trees (1997)
    • Dynamic Hash Tables (1988)
    • LFU Implementation With O(1) Complexity (2010)
    • Time, Clocks, and the Ordering of Events in a Distributed System (1978)
    • Dapper, a Large-Scale Distributed Systems Tracing Infrastructure (2010)
    • Gorilla: A Fast, Scalable, In-Memory Time Series Database (2015)
  • Release It 笔记
    • Anti-patterns & Patterns in Microservice Architecture
  • Database Design
    • Log Structured Merge (LSM) Tree & Usages in KV Stores
    • Prometheus
Powered by GitBook
On this page
  • Securing Communication: Cryptography
  • Using Symmetric Keys
  • Asymmetric Encryption (Public Key)
  • HTTPS
  • Cloud Computing
  • 参考
  1. UCB - CS162

Security & Cloud Computing (24)

PreviousDistributed Storage, Key-Value Stores, Security (23)NextTopic: Ensuring Data Reaches Disk

Last updated 5 years ago

Securing Communication: Cryptography

Using Symmetric Keys

对称加密使用相同的 key 来加密 (encryption) 和解密 (decryption),如下图所示:

这种加密容易被 tampering 和 replay attacks 破解。

XOR

一种简单的加密方式可以直接对消息与 key 执行 XOR 操作,这种方案实现很容易,但也容易被频度分析 (frequency analysis) 破解。

为了改善上述方案,可以对不同的消息使用不同的 key 加密,但这就要求双方都能够知道具体使用的 key。

Block Cipher

更复杂的加密算法通常将消息分段 (block) 加密:

DES & AES

Data Encryption Standard (DES) 在 19 世纪 70 年代由 IBM 研发,由 NBS/NIST 标准化。它使用长度为 56 bits 的 key 进行加密。但一些定制化的硬件可以在 24 小时内将其破解,如今许多金融机构使用 Triple DES 进行加密,key 的长度达到 168 bits。

Advanced Encryption Standard (DES) 是 2002 年提出的 DES 的替代算法,它使用长度为 128,192 或 256 bits 的 key 对数据进行加密。它的加密强度并没有被严格证实,但已经被广泛使用。

Authentication via Secret Key

A 与 B 相互通信,需要向对方证明自己的身份。利用对称加密:

  • A 和 B 事先商量好一个共同的 secret key

  • A 生成一个随机数 x,然后用 key 加密后发送给 B

  • B 用 key 解密消息后将随机数返回给 A

如下图所示:

这种验证方式容易被中间人 (man-in-the middle) 攻击。

Integrity: Cryptographic Hashes

另一个加密算法的使用场景就是验证数据的完整性。可以利用加密哈希算法将正确的数据计算一次 hash,数据接收方获取数据后只要重新计算一遍 hash 验证二者是否相等即可。

数据发送方使用 H(x) 求数据的 digest,即上文的 hash,的方案如下:

  • H(x) 是一个大家都知道的哈希函数

  • Digest d = HMAC(K, m) = H(K | H(K | m))

当接收方获取消息后,使用共享的 secret key K 来重新计算 HMAC(k, m) 并比对即可。

一些标准的加密哈希函数罗列如下:

名称

说明

MD5 (Message Digest version 5)

  • 研发于 1991 年

  • 产生长度为 128 bits 的 hashes

  • 被广泛使用 (RFC 1321)

  • 可被破解 (1996 - 2008):可能出现 collisions

SHA-1 (Secure Hash Algorithm)

  • 研发于 1995 年,是 MD5 继承者

  • 产生长度为 160 bits 的 hashes

  • 被广泛使用于 (SSL/TLS, SSH, PGP, IPSEC)

  • 在 2005 年被破解,政府部门已经在 2010 年停用该算法

SHA-2 (2001)

包含一系列算法,SHA-224,SHA-256,SHA-384, SHA-512

Asymmetric Encryption (Public Key)

非对称加密的核心思想是利用两个 key,一个用来加密 (e),一个用来解密 (d),并且要求两个 key 不能互相推导,即知道 e 并无法推导出 d。这样 e 可以被公开,即所谓公钥。这时候,消息加密与解密的过程如下所示:

假如 Alice 想要向 Bob 发送消息,她就需要先获取 Bob 的公钥 (公开),并且利用公钥加密消息。即便 Alice 是加密消息的人,她也无法解密消息,世界上只有 Bob 能够利用私钥解密 Alice 发送的消息。抽象地说:

  • 发送方利用接收方的公钥加密数据

  • 接收方利用私钥解密数据

非对称加密在 19 世纪 70 年代被提出,它的原理来自于数论 (Number Theory)。最成熟的方案是 RSA,由 Rivest、Shamir 和 Adleman 在 1977 年提出,并写入 RFC 3447。另外一个成熟的方案是 ECC (Eliptic Curve Cryptography),基于 Galois-field space 的曲线原理,使用的 key 比 RSA 更短。

RSA 需要生成很大的随机质数、求大数的指数值,现已存在效率较高的算法能够生成它们。总体上,RSA 比对称加密方案的速度要慢很多。

Public Key Authentication

利用非对称加密做身份验证的过程如下图所示:

A 和 B 互相知道对方的公钥:

  1. A 生成一个随机数 x,用 B 的公钥将自己的身份 A,随机数 x 一同加密,发送给 B

  2. B 用自己的私钥解密消息,同时生成一个随机数 y,将 x、y 以及自己的身份 B 用 A 的公钥加密后发送给 A

  3. 这样 A 就知道 B 是 B,但 B 尚未知道 A 是 A。这时,A 需要将 B 生成的随机数和自己的身份 A 用 B 的公钥加密后一同发送给 B

这时候,A 和 B 之间就能够互相确信对方身份。

Non-Repudiation: RSA Crypto & Signatures

假设 Alice 有一个公钥 KE,如果她想证实自己是谁,可以直接将消息 m 用自己的私钥加密后发送出去,由于 Alice 的公钥已经公开,那么大家就可以通过她的公钥验证这条消息的来源。此时 Alice 已经无法否认自己发送的消息,这种性质被称为 non-reputation。

Digital Certificates

这种方式也可以用来产生文档的电子签名。但产生电子签名时,我们如何知道 Alice 的公钥真的是她的公钥,而不是其它人在欺骗我们?

这时就需要一个可以信赖的第三方机构 (Trusted Authority),负责为大家的公钥签名,然后以电子证书 (digital certificate) 的形式发布,这样每个人都可以用 TA 的公钥来验证证书中的信息是否正确。

那么我们又如何知道 TA 的公钥真的是它的公钥?TA 的公钥会被编译进浏览器的源码中,因此这一层保护浏览器会帮我们做。(HTTPS)

HTTPS

先引入一些概念:

  • HTTPS: Use HTTP over SSL/TLS

  • SSL: Secure Socket Layer

  • TSL: Transport Layer Security (successor to SSL), 在 TCP 之上提供一层加密抽象层 (authentication, encryption)

当你访问 https://www.amazon.com 时,发生了什么?

  • 浏览器 (Client) 通过 TCP 与 Amazon HTTPS 服务器建立连接 (TCP 连接)

  • Client 发送一系列自己支持的加密协议给 Server

  • Server 从列表中选择一个,并将自己的证书发送给 Client。证书中的信息包括

    • 名称 (Amazon)

    • Amazon 的 RSA 公钥

    • 其它附带信息,如 Amazon 的地址、证书类型以及过期时间

    • 发证方

    • 以及以上所有信息的签名

  • Client 验证证书是否有效

整个原理如下图所示:

验证证书有效后,Client 和 Server 之间还需要商量一个 session key 用于后续的消息传输:

  • 浏览器 (Client) 生成一个随机数 K 作为 session key (用于后续的数据传输),用 Server 的公钥加密后发送给 Server

  • Server 表示同意

至此 Client 与 Server 之间就完成了验证和 session key 的确认,后续的消息直接用对称加密的方式进行即可。

Cloud Computing

本节略,主要就是一些基本介绍,没有多少实质内容。

参考

lecture note

24