ソフトウェアエンジニアの技術ブログ：Software engineer tech blog

48 bits => 32 bits(8*6 => 8*4)
2 bits used to select amongst 4 substitutions for the rest of the 4-bit quantity

Security of DES
– key space is too small(2^56 keys)
Exhaustive key search relative easy with today’s computer
– S-box design criteria have been kept secret
– Highly resistant to cryptanalysis techniques published years after DES

Triple DES
(a)Encryption p -> E -> D -> E -> C
(b)Decryption: C -> D -> E -> D -> P
K1=K3 result in an equivalant 112-bit DES which provides a sufficient key space
Distinct K1, K2, K3 results in an even stronger 168-bit DES
Can run as a single DES with K1 = K2

Advanced Encryption Standard
In 1997, the U.S. National Institute for Standards and Technology(NIST) put out a public call for a replacement to DES
It narrowed down the list of submissions o five finalists, and ultimately chose an algorithm(Rijndael) that is now known as the Advanced Encryption Standard
New (Nov. 2001) symmetric-key NIST standard, replacing DES
Processes data in 128 bit blocks
Key length can be 128, 192, or 256 bit

Block cipher primitives
DES
AES
Encrypting large message
Message integrity

Block Cipher Scheme
plaintext block of length n -> Encrypt -> cipher block of length n

Block Cipher Primitives
Confusion:
an encryption operation where the relationship between the key and ciphertext is obscured
achieved with substitution

Diffusion
an encryption operation where the influence of one plaintext bit is spread over many ciphertext bits with the goal of hiding statistical properties of the plaintext
achieved with permutation

Both confusion and diffusion by themselves cannot provide (strong enough) security
Round: combination of substitution and permutation, and o so often enough so that a bit change can affect every output bit

Data Encryption Standard
64 bit M -> DES Encryption -> 64 bit C
56 bits
Published in 1977, standardized in 1979
Key:64 bit quantity=8-bit
parity+56-bit key
Every 8th bit is a parity bit
64 bit input, 64 bit output

Data Encryption Standard
DES Top view
64-bit input
permutation
round1
round2
swap
permutation
64-bit output

Bit permutation(1-to-1)
Input <-> Output

DES Round
32 bits Ln, 32 bit Rn
Can be expressed as: Ln+1 = Rn, Rn+1 = LnXORM(Rn,Kn)

Decryption
-Apply the same operations key sequence in reverse
Round1 of decryption uses key of the last round in encryption
-Each round:
Input: Rn+1|Ln+1
Due to the swap operation at the end of encryption
Output:Rn|Ln
The swap operation at the end will produce the correct result:L|R

Mangler Function
The permutation produces “spread” among the chunks/S-Boxes!

– protects a message without needing to first arrange for sender and receiver to have the same secret key
– Equates to the same thing as a sealed envelope containing an unsigned letter

Message
random symmetric key -> encrypted message -> digital envelop
receiver’s public key -> encrypted symmetric key -> digital envelope

plaintext input -> encryption algorithm -> decryption algorithm(reverse of encryption algorithm)-> plaintext output

y = E[K,X], X=D[K,Y]

Comparison of Encryption Algorithm
DES = Data Encryption Standard
AES = Advanced Encryption Standard

Plaintext block size(bits)
Ciphertext block size(bits)
Key size(bits)

Asymmetric Encryption
– plain text:readable message or data that is fed into the algorithm
– encryption algorithm: perform transformations on the plaintext
– public and private key: pair of keys, one for encryption, one for decryption
– ciphertext: scrambled message produced as output
– Decryption key: produces the original plaintext

Digital Signatures:
plaintext message -> hash function -> hashtag -> encrypted signed message -> compare the hash value sent with hash value generated -> reject message

Generate hash code of unsigned certificate -> Encrypt hash code with CA’s private key to form signature -> signed certificate -> decrypt signature with CA’s public key to recover hash code -> recepient can verify signature by comparison hash code values

Simple Ciphers
– Caesar’s cipher(or, shift cipher):
e.g., A->D, B->E
that is, shift by an offset n:
-(letter + n) mod 26
only 26 possible ways of secret coding
– Monoalphabetic cipher(or, substitution cipher):
generalization, arbitrary mapping of one letter to another
26!, ~4*10^26 or ~ 2^88
Attack with statistical analysis of letter frequencies

Vigenere Cipher

What should be kept secret?
Kerchhoff’s principle
a cryptosystem should be secure even if the attacker knows all details about the system, with exception of the secret key
In practice:
Only use widely known ciphers that have been crypto analyzed for several years by good cryptographers
e.g., established standards

secret key cryptography:
one key same key for encryption and decryption
public key cryptography:
two keys
public for encryption, private for decryption
private for signing and public for verification

Hash Functions
compute message digest of data of any size
fixed length output: 128-512 bits
easy to compute H(m)
Given H(m), no easy way to find m
– one-way function
Given m1, it is computationally infeasible to find m2=m1 s.t. H(m2)= H(m1)
weak collision resistant
Computationally infeasible to find m1 = m2 s.t. H(m1)=H(m2)
strong collision resistant

Hash Functions for passwords
hash function, stored hash of password -> access granted

Encryption/Decryption

plaintext -> Encryption -> ciphertext -> Decryption -> plaintext

there is a one-to-one mapping
provides confidentiality protection

Other services:
Integrity checking: no tampering
Authenticity: verified authorship
Authentication: not an imposter

Encryption basics
ancient crypto:
early sings of encryption in Egypt in ~2000 B.C.
letter-based scheme (e.g., Caesar’s cipher) ever since

Symmetric ciphers:
from ancient time to the presence
Asymmetric ciphers:
first by diffie-Hellman-

– Resource exhaustion
– cpu resources
– memory
– Network bandwidth

– Abusing reactive IDS
– false positives
– nuisance attacks or “error” packets/connections

Intrusion Prevention System(IPS)
also known as intrusion detection and prevention system(IDPS)
is an extension of an IDS that includes the capability to attempt to block or prevent detected malicious activity
can be host-based, network-based, or distributed/hybrid
can use anomaly detection to identify behavior that is not that of legitimate users, or signature/heuristic detection to identify known malicious behavior can block traffic as a firewall does, but makes use of the types of algorithms developed for IDSs to determine when to do so

P(I) is base rate: prior probability of attacks

base-rate fallacy
– even if false alarm rate P(A|¬I) is very low, Bayesian detection rate P(I|A) is still low if base-rate P(I) is low
– E.g. if P(A|I)=1, P(A|¬l)=10^-5, P(I)=2×10^-5, P(I|A)=66%

When the IDS produces an alert, the probability that an intrusion has actually occurred is low.

Implications to IDS
– Design algorithms to reduce false alarm rate
– Deploy IDS to appropriate point/layer with sufficiently high base rate
– Multiple independent detection models

Architecture of Network IDS
– Packet data volume can be huge
– Base rate at the packet level is typically low
– Applying detection algorithms at this level may result in a low bayesian detection rate

Network -> libcap -> Event Engine -> Detection Engine

Eluding Network IDS
What the IDS sees may not be what the end system gets
Ambiguities in protocols lead different implementations in operating systems:
E.G, TTL, fragments

Detection rate or True Positive(TP) rate:
given that there is an intrusion, how likely will the IDS correct output an alert.

False Negative Rate: FN = 1- TP

False alarm or False Positive(FP) rate:given that there is no intrusion, how likely is the IDS to falsely output an alert.

True Negative Rate: TN = 1 – FP

Bayesian detection rate: given that the IDS produces an alert, how likely is it that an intrusion actually occurs?

Alarm/positive: A; Intrusion: I
Detection (true positive) rate: P(A|I)
false negative rate P(¬A|I)
False alarm rate: P(A|¬I)
true negative rate P(¬A|¬I)
Bayesian detection rate: P(I|A)

System should be: scalable, resilient to attacks

Bayesian Detection Rate
P(I|A) = P(I)P(A|I)/P(I)P(A|I)+P(¬I)P(A|¬I)
P(I) is prior probability of attacks: this is the probability of intrusion evidences in the data.

(a)Rule header
Action, Protocol, Source IP Address, Source Port, Action, Dest IP address, Dest Port

(b)Options
Option Keyword, Protocol Arguments

Meta-data:provides information about the rule but do not have any effect during detection
Payload:look for data inside the packet
Post-detection: rule-specific triggers that happen after a rule has matched a packet

snort rule actions
alert, log, pass, activate, dynamic, drop, reject, sdrop

snort rule example
alert tcp any any -> 192.168.1.0/24 25(content:”mail from:root”;msg:”root users attempts to send an email”;)

Honeypots
Honeypots are decoy systems designed to lure attackers away from critical systems

Honeypots are designed to:
divert an attacker
collect information about an attacker
encourage an attacker to stay long enough for administrators to respond

Honeypots are filled with fabricated information
Any accesses to a honeypot trigger monitors and event loggers
An attack against a honeypot is made to seem successful

A honeypot has no production value
there is no legitimate reason to access a honeypot
any attempt to communicate with a honeypot is most likely a probe, scan, or attack
if a honeypot initiates outbound traffic, the system is most likely compromised