Cryptography Part III
Mar 12 SPN & AES
SPN
SPN are built along Shannon’s criteria of confusion and diffusion
Confusion: obtained from the key mixing and substitution phase
make the relationship between the key and cipher text as complicated as possible. Which means given cipher text it is hard to derive the key
Diffusion: obtained through the permutation of linear diffusion phase
dissipating the statistical structure of plaintext over the bulk of ciphertext. Which means the attacker could not break the system by statistic methods
AES
- 128-bit block size (thought as a 4×4 byte matrix)
3 key sizes (128/192/256-bits)
Round Structure: Given a 4*4 byte matrix as input
A Substitution layer in the form of 16 S-boxes, 8-to-8 bit
A Permutation layer implemented via a bytewise rotation (ShiftRows) and a xor-linear operation among state bytes (MixColumn)
A key addition: bitwise ⊕, with 128 bits of expanded key material
Steam Ciphers
In a Stream Cipher, we would like to
use short keys k ∈ K to encrypt long messages
use algorithmically generated pseudo-random values for the keystream instead of truly random ones
be sure that the same keystream sequence is repeated only after a very long sequence of messages has been encrypted (. . . a practical value for infinity)
Synchronous Stream Ciphers
The keystream is generated as a function of the cipher key and of the memory elements, independently of any previous ptx or ctx digit, i.e. ki=f(k,s0,s1,…)
Asynchronous Stream Ciphers
The keystream is generated as a function of the cipher key and a finite number of previous ctxs.
Given a key k and an initial state S0 = ⟨sL−1, . . . , s0⟩ the keystream is composedas: ki =f(k,Si,Si−1,…)with Si =⟨ci+L−1,ci+L−2,…,ci+1,ci⟩
LFSR/Linear Feedback Shift Registers
https://www.youtube.com/watch?v=sKUhFpVxNWc
Mar 15 Hybrid Cryptosystems
Hybrid cryptosystems
Encryption: Alice generates a random symmetric key k, encrypts the message with it, and encrypts k with kBpub
Decryption: Bob decrypts k using kBpri, and uses it to decrypt the message, after which he may discards k.
Signature: Alice should sign something smaller than the whole message, although uniquely bound to it in some way
Solving the efficient signature problem requires a new cryptographic primitive, the cryptographic hash
Cryptographic Hash
A hash is a deterministic function from arbitrary length message m, to fixed length output h = H(m) (Practically used to obtain a fixed-length “label” h for a digital object)
The same value of h may be the hash of different messages (no such thing as bijective arbitrary size → fixed size compression)
Property
Given h, hard to find m such that H(m)=h
Given m, hard to find m’ such that H(m)=H(m’)
Hard to find m’ and m’’ such that H(m’)=H(m’’)
Public Key Authentication[证明公钥匙是谁的]
To prevent impersonation attack on publich key cryptosystems.(Pretend to be someone you are not and steal the information). Here rises the need of DIGITAL CERTIFICATE of authenticity of public keys
Digital Certificate
Our purpose is to authenticate the binding of a public key to the identity of someone/some company
举个例子方便大家理解，假设我们公司”ABC Company”花了1000块钱，向一个证书发布机构”SecureTrust CA”为我们自己的公司”ABC Company”申请了一张证书，注意，这个证书发布机构”SecureTrust CA”是一个大家公认并被一些权威机构接受的证书发布机构，我们的操作系统里面已经安装了”SecureTrust CA”的证书。”SecureTrust CA”在给我们发布证书时，把Issuer,Public key,Subject,Valid from,Valid to等信息以明文的形式写到证书里面，然后用一个指纹算法计算出这些数字证书内容的一个指纹，并把指纹和指纹算法用自己的私钥进行加密，然后和证书的内容一起发布，同时”SecureTrust CA”还会给一个我们公司”ABC Company”的私钥给到我们。我们花了1000块钱买的这个证书的内容如下：
×××××××××××××××证书内容开始×××××××××××××××××
Issuer : SecureTrust CA
Subject : ABC Company
Valid from ： 某个日期
Valid to： 某个日期
Public Key : 一串很长的数字
…… 其它的一些证书内容……
{证书的指纹和计算指纹所使用的指纹算法}[SecureTrust CA的私钥|RSA]
//这个部分验证了消息的完整性，确定这个消息没有被人中途修改过
//这个就是”SecureTrust CA”对这个证书的一个数字签名，表示这个证书确实是他发布的，有什么问题他会负责(收了我们1000块，出了问题肯定要负责任的)
×××××××××××××××证书内容结束×××××××××××××××××
//{} 表示RSA加密后的内容，[ | ]表示用什么密钥和算法进行加密
首先当用户收到了来自一个服务器的一个安全证书，他会检查是否CA是这个用户信任的CA
其次用户会检查这个安全证书是否是权威的，也就是通过CA公布的公钥来验证CA的数字签名
如果用户确认了这一消息（该证书由一个可信赖的CA颁发并且内容没有修改过），那么这份安全证书就可以被信任
A keypair can be compromised (e.g. by theft, blackmail)。 Revocation of a certificate could be done by CRLs, or OCSP.
Who Signs The Certificate
PKI/Public Key Infrastructure: A centralized, tree structured
architecture of entities which sign certificates of their subsiders. The root authorities are implicitly trusted
Root CAs are a single point of failure for the whole infrastructure: if a Root CA gets its key compromised, all the certificates issued from offspring CAs become forgeable.
ACME Control
WoT/Web-of-Trust: A distributed architecture relying on the “small world assumption” where everyone can sign certificates. The trust on the authenticity of a certificate is established depending on the trust on the authenticity of its signers
Users: The only actor of the scheme are users, they :
Encrypt/sign/verify a digital object (file/mail message)
Acts as a CA signing someone else’s key/id pair
Keep a local key/id keyring where all the certificates are kept
Choose which users they trust to be acting as a CA
Keyservers: Provide a globally synchronized, trusted archive of public certificates.
Public lookup is provided via either key ID or user ID
The archive is append only, no practical removal is possible
Anyone can run a keyserver, provided he has enough resources.
Trust Levels:
The default trust levels in the WoT scheme are :
ultimate: It’s the user’s own key trust level. Every key you sign with an “ultimate” trusted key becomes authentic.
complete: One signature by a key with this level of trust makes the key/id pair authentic.
marginal: At least 2 keys with marginal trust have to sign a key/id pair to make it authentic.
untrusted: Untrusted key signatures do not contribute to mark a key/id pair as authentic
This based on the assuming that before a certificate is signed, each user would be careful enough to verify the corresponding identity.
Certification Authority (CA): An entity (typically a firm) which takes care of signing the certificates, and distributes its public key to all the users in a trusted manner
The CA creates its own keypair and fills in the fields of its certificate
We assume, for the sake of clarity, that we are describing a root CA, i.e. one sitting at the top of the PKI hierarchy The CA self-signs its own certificate, and stores its own private key in a tightly guarded place (at least,hopefully)
The CA takes care to distribute its self-signed public key certificate in a safe manner to the largest possible user-base
Registration Authority (RA): An entity (again, usually a firm) which takes care of verifying the actual authenticity of a certificate, gathering data on the user (physically checking his/her identity and certificate hash). Very often, it coincides with the CA
User: Asks the CA to sign his certificate, or employs the CA public keys to verify the authenticity of the certificates for another user.
Mail Protocol PGP/GPG
Possible to encrypt and sign any file, the most typical use is to encrypt and sign e-mail messages
PGP/GPG messages encrypted and signed with an hybrid symmetric+asymmetric scheme for efficiency
This method is the typical hybrid system. Sender generates a symmetric key to encrypt files and send the symmetric key encrypted in the reciever’s public key.