Computer Security Exam
Malikbinn
CPSC353PowerPoints-B.zipCh10-DRM.pptx
Digital Rights Management
12/1/2010
Digital Rights Management
1
1
Introduction
Digital Rights Management (DRM) is a term used for systems that restrict the use of digital media
DRM defends against the illegal altering, sharing, copying, printing, viewing of digital media
Copyright owners claim DRM is needed to prevent revenue lost from illegal distribution of their copyrighted material
12/1/2010
Digital Rights Management
2
2
DRM Content and Actions
There are many capabilities covered by DRM
12/7/2010
Digital Rights Management
3
Possible Actions and Restrictions:
Play once
Play k times
Play for a set time period
Play an unlimited amount
Copy
Burn to physical media
Lend to a friend
Sell
Transfer to a different device
Digital content:
Videos
Music
Audio books
Digital books
Software
Video games
Digital Rights Management
Early U.S. Copyright History
US Constitution, Article 1, Section 8
“The Congress shall have the Power … To promote the Progress of Science and useful Arts, by securing for limited Times to Authors and Inventors the exclusive Right to their respective Writings and Discoveries”
Copyright Act of 1790
"the author and authors of any map, chart, book or books already printed within these United States, being a citizen or citizens thereof....shall have the sole right and liberty of printing, reprinting, publishing and vending such map, chart, book or books...."
Citizens could patent books, charts, or maps for a period of 14 years – Could renew for another 14 years if you were alive
Non-citizens and works form other countries not protected
Other laws followed to change the Act slightly
12/1/2010
Digital Rights Management
4
Copyright Act of 1976
Could copyright literary works, musical works, dramatic works, choreographic works, graphical works, motion pictures, and sound recordings (architectural works added in 1990)
Copyright holders had exclusive right to reproduce, create derivative works of the original, sell, lease, or rent copies to the public, perform publicly, display publicly
Could hold copyright for 28 years with a possible 28 year extension
Rights of copyright holders are limited slightly by sections 107 through section 118 – Often referred to as Fair Use
12/1/2010
Digital Rights Management
5
Fair Use Doctrine
Various purposes for which reproducing a particular work is considered fair use
Criticism, comment, news reporting, teaching, scholarship and research
Four factors are considered when determining if it is fair use [17 U.S.C. § 106]
The purpose and character of the use, including whether such use is for commercial nature or is for nonprofit educational purposes;
The nature of the copyrighted work;
The amount and substantiality of the portion used in relation to the copyrighted work as a whole; and
The effect of use upon the potential market for or value of the copyrighted work
12/1/2010
Digital Rights Management
6
Sony vs. Universal Studios
In the 1970s, Sony invented Betamax, a video tape recording format similar to VHS
Could be used to record copyrighted broadcasts
At the same time, some movie studios created Discovision which was a large disk that would disintegrate after a few plays
In 1976 Universal Studios and Disney sued Sony for all the lost profits and tried to ban the use of Video Tape Recorders (VTR)
District Court for the Central District of California rejected the claim on the basis that noncommercial use of VTRs was considered fair use
Court of Appeals for the Ninth Circuit reversed the ruling and held Sony liable for aiding in copyright infringement
12/1/2010
Digital Rights Management
7
Sony vs. Universal Studios (cont.)
In 1984, the Supreme Court had to decide on the issue – Is selling VTRs to the general public aid in copyright infringement of public broadcasts?
The Supreme Court eventually ruled that “the sale of the VTR’s to the general public does not constitute contributory infringement of copyrights”
Concluded that most copyright holders who license there work for public broadcast would not mind having their broadcasts recorded on to a Betamax tape by viewers
Betamax was ruled that it fell under the Fair Use clause
Case often referred to by future copyright lawsuits including the Napster case
12/1/2010
Digital Rights Management
8
Digital Millennium Copyright Act (DMCA)
Signed into law by President Clinton on October 28th, 1998
Illegal to circumvent anti-piracy measures built into software
Unlawful to create, sell, or distribute devices that illegally copy software
Legal to crack copyright protection to conduct encryption research, assess product interoperability, and test computer security systems
Provides exceptions to nonprofit libraries, archives, and educational institutions in some cases
ISPs are not held accountable for transmitting information resulting from their customers infringements
Service providers are required to remove material when found
Congress passed the law with almost no opposition
Congress held the impression that it was merely a technical issue and not one of impact to public policy
Highly lobbied by the industry
12/1/2010
Digital Rights Management
9
Dmitry Skylarov and Ed Felten
Dmitry Skylarov
Worked for Elcomsoft in Russia and created product that converts Adobe secure eBook to unprotected PDF (legal in Russia)
While in the US, Skylarov was arrested and placed in jail for DMCA violations
Eventually Elcomsoft was sued and Skylarov was released
Professor Edward Felten of Princeton
In 2000, the Secure Digital Music Initiative (SDMI) invited researchers to try and break their watermark technology
Felten and his team were able to remove the watermarks and wrote a paper to be presented at a conference
SDMI and RIAA threatened to take legal action against Felten
Felten withdrew from conference but talked about the threats
Felten with help of the Electronic Frontier Foundation sued RIAA and SDMI
SDMI and RIAA withdrew their threat
Felten eventually presented the paper at a different conference
12/1/2010
Digital Rights Management
10
Copy Protection Methods
Dongle
Pluggable hardware device that contains a secret value required to run the software
Product key
Required to be entered by installation software
Online check for duplicate use
Hardware and OS fingerprinting to bind license to machine
Phone activation
Human-to-human interaction servers as deterrent
12/1/2010
Digital Rights Management
11
The Analog Hole
Every copy protection mechanism is open to the risk of the “analog hole”, that is, recording the content as it is being played
12/7/2010
Digital Rights Management
12
analog
hole
DRM Media File Example
Step 1:
A media server sends to the player the media file encrypted with the file key and the file key encrypted with the player key
12/7/2010
Digital Rights Management
13
Player
Server
Unprotected Storage
C
encrypted media file
G
encrypted file key
C
G
DRM Media File Example
Digital Rights Management
14
Player
Unprotected Storage
M
media file
P
player key
Decrypt
C
G
F
file key
Decrypt
Step 2:
The player first decrypts the file key using the player key and then decrypts the media file with the file key.
Traitors Tracing
A controller distributes protected content to a collection of devices
The devices share a common symmetric key with the controller
Each content item is encrypted with the shared key and broadcast to all the devices
Some devices (traitors) are cloned or used to illegally copy and distribute protected content
Problems:
Identifying traitors
Revoking traitors
12/1/2010
Digital Rights Management
15
Logical Key Hierarchy
Balanced binary tree of symmetric encryption keys
Devices associated with leaves, each holding the keys on the path to the root
Content encrypted with the key of a node v can be decrypted by all the devices in the subtree of v
12/1/2010
Digital Rights Management
16
K2
K3
K4
K5
K1
Revocation of a Device
If a device needs to be revoked, the keys known to this device must be changed and the new keys must be distributed
The distribution of new keys can be done with a logarithmic number of encrypted broadcast messages
12/1/2010
Digital Rights Management
17
Encrypted Broadcasts
Content hierarchy with various subscription packages
Each content item is encrypted with a single symmetric key before broadcasting
Subscriber authorized to view item must have the key to decrypt the item
Single key per node allows computation of keys of descendant nodes
Key distribution problem
12/1/2010
Digital Rights Management
18
Sport
Economy
News
Local
US
World
Finance
Business
All
CD/DVD Protection
Most CD/DVDs are protected so they cannot be copied
CDs are not indestructible and backups are required
Legal to make backups of CDs you own in most countries – Not legal to sell
Most protection technologies encrypt the files using a key that is added to the disc as a digital signature
Almost every encryption technique has been cracked
12/1/2010
Digital Rights Management
19
CD/DVD Protection
Technically, it is impossible to completely prevent users from copying media they purchase
Bit-by-bit copy of software
Recording of music using microphones
Recording of movies using cameras
Scanning of text media
Given enough time and resources, any media can be copied
Most companies realize they cannot stop “professionals” from duplicating but they try to stop the casual user from copying
12/1/2010
Digital Rights Management
20
SafeDisc V1 and V2
Copy protection created by MacroVision
Games starting in 1999 were protected
Based on having read errors on the original disc
CD burners had to be able to copy the errors exactly as is
Version 2Has bad sectors like version 1 but also has “weak” sectors
Weak sectors often become bad sectors when copying
Uniform bit-patterns are hard to write for many CD writers – Some people allege hardware manufacturers may have done this on purpose to aid CD copy protection
Easy to break
1:1 CD-Copy using several CD copy programs
SafeDisc Patches: Generic SafeDisc Patch, Daemon Tools
Executable UnWrappers: unSafeDisc, DumPlayerx
12/1/2010
Digital Rights Management
21
DVD copy protection
Traditional recording media (e.g., audio tape, VHS tape) for audio and video are analog and used different standards NTSC, PAL, SECAM ...
Piracy is not too big of a concern because quality degrades with each copy generation.
With digital recording and high-resolution video, DVD copy protection was a big issue to the movie industry.
In fact, it took about 2 years after the invention of DVD to put DVD movies on the shelf. Part of it is due to the development of a reasonable copy protection scheme.
12/1/2010
Digital Rights Management
22
How Studios Split our Planet
12/1/2010
Digital Rights Management
23
DVD Region Code Symbol
A region code byte is recorded on a disc
DRM Architecture
Proposed by the Copy Protection Technical Working Group for DVD (CPTWG), IBM, Intel, Matsushita, Toshiba.
Idea:
Alice sells Bob a video, in order for Alice to prevent Bob from re-disseminating the video to others, Alice tries to make sure that Bob only accesses the video data on a trusted (or compliant) device
12/1/2010
Digital Rights Management
24
Trusted Devices
A trusted device is manufactured by a trusted manufacturer.
A manufacturer is trusted if it has joined the Copy Control Association (CCA)
A trusted device is given a (secret) player key
The trusted manufacturer has to sign an agreement with CCA, basically barring it from making devices that could undermine the copy protection mechanism.
Since 2000, manufacturers must produce DVD ROM drivers compliant with=RPC 2 (Region Playback Control)
12/2/2010
Digital Rights Management
25
In most cases, a DVD (video disk) is protected by the CSS scheme. Intuitively, the video content is encrypted using a disc key, k.
In the lead-in area of a CSS-protected DVD, the disk’s key k is encrypted about 400 times, each using a different player key.
A DVD player with the ith player key will read the ith entry of the key block. This entry is then decrypted using the player key ki to obtain the disk key k.
The video content is then decrypted on-the-fly while the movie is played.
Using a normal DVD writer the copy will not have the key block and disk will not be playable
if someone decrypts a video, with special tools (HW or SW), it is possible make pirated copies with the lead-in key block or without CSS (i.e., decrypted).
CSS: Content Scrambling System
12/2/2010
Digital Rights Management
26
Lead-in
with
Key block
copy
decrypt and write
unencrypted
Lead-in
without
Key block
26
Viewing a DVD
12/2/2010
Digital Rights Management
27
Encrypted Content
Disc Key
Title Key
Encrypted Content
Title Key
Player Key
Decrypt Disc Key
Decrypt Title Key
Decrypt Content
(To Output Device)
CSS Keys
Authentication Key
Used for mutual authentication
Session/Bus Key
negotiated during authentication
encrypt title and disk keys before sending them over the unprotected bus
Prevent eavesdropping
Player Key
Licensed by the “DVD Copy Control Association” to the manufacturer of a DVD player
Stored within the player
Authenticates the player
Used to decrypt disk key.
Disk Key
Used to decrypt the title key
Title Key
This key is XORed with a per-sector key to encrypt the data within a sector
Sector Key
Each sector has a 128-byte plain-text header
Bytes 80 - 84 of each sector’s header contain an additional key used to encode the data within the sector
12/2/2010
Digital Rights Management
28
DeCSS
Created in 1999 by Jon Johansen
Decrypts CSS and allows for copying files to hard drive
At the time, little information known about CSS algorithm
DeCSS came with the source code that showed how easy it was to crack CSS
Technique used for creating open source DVD players that could run on Linux
First in a long line of DVD decrypting programs
Johansen was sued by the DVD-CCA but case was dropped
Mass pirating occurred far before DeCSS was published
DVD writers are unable to write to the region that CSS writes
Most DVD copies done using special equipment that copy bit by bit
12/2/2010
Digital Rights Management
29
Advanced Access Content System
New standard for DRM that allows for limited sharing and copying of next generation DVDs
Developed by Microsoft, Sony, Disney, IBM, Matsushita, and Warner Brothers
Used in Blu-Ray
Method
Based on broadcast encryption
Revocation of traitors
12/2/2010
Digital Rights Management
30
Ch08-DataIntegrity.pptx
Data Integrity: Applications of Cryptographic Hash Functions
12/7/2010
1
Data Integrity
Message Authentication Code (MAC)
Cryptographic hash function h(K,M) with two inputs:
Secret key K
Message M
Message integrity with MAC
Sequence of messages transmitted over insecure channel
Secret key K shared by sender and recipient
Sender computes MAC c = h(K,M) and transmits it along with message M
Receiver recomputes MAC from received message and compares it with received MAC
Attacker cannot compute correct MAC for a forged message
More efficient than signing each message
Secret key can be sent in a separate encrypted and signed message
12/7/2010
Data Integrity
2
M
c
sent message
Compute c = h(K,M)
Compute d = h(K,M′)
Accept if d = c′
M′
c′
received message
HMAC
Building a MAC from a cryptographic hash function is not immediate
Because of the iterative construction of standard hash functions, the following MAC constructions are insecure:
h(KM)
h(MK)
h(KMK)
HMAC provides a secure construction:
h(K Ah(K B M))
A and B are constants
Internet standard used, e.g., in IPSEC
HMAC security is the same as that of the underlying cryptographic hash function
12/7/2010
Data Integrity
3
Securing a Communication Channel
Assuring both integrity and confidentiality of messages transmitted over an insecure channel
Sign and encrypt
The encrypted pair (message, signature) is transmitted
MAC and encrypt
The encrypted pair (message, MAC) is transmitted
Secret key for MAC can be sent in separate message
More efficient than sign and encrypt
MAC is shorter and faster to compute than signature and verification
Alternatively, signing or applying MAC could be done on encrypted message
12/7/2010
Data Integrity
4
M
sig
M
MAC
encrypted
encrypted
Hash Chain
Repeated cryptographic hashing starting from a random value r
xn = r
xi = h(xi +1) for i = n-1 … 1
Sequence x1 x2 … xn is pseudo-random
Applications
One-time passwords
Incremental micropayments (PayWord)
Key property for security is preimage resistance of hash function
5
x2
x3
x4
x5
x6
x1
hash
reveal
12/7/2010
Data Integrity
Validation Chain
Validation chain over a sequence of plaintexts p1, p2 , …, pn
xn+1= 0
xi = h(pi || xi+1 ) for i = n … 1
Incremental stream authentication [Gennaro Rohatgi]
transmit signed x1
transmit packets (p1, x2), (p2, x3), …, (pn-1, xn), (pn, xn+1)
each packet contains the hash of the next packet
the integrity of the first hash implies the integrity of the rest
any prefix of the stream is signed and cannot be repudiated
constant overhead (one hash per plaintext)
one signature (slow), n hash computations (fast)
offline method, requires reliable transmission
6
p1, x2
p2, x3
p3, x4
p4, x5
p5, 0
sig, x1
12/7/2010
Data Integrity
Hash Tree
Balanced binary tree defining a hierarchical hashing scheme over a set of items
a = h(x1, x2)
b = h(x3, x4)
c = h(a, b)
…
The root hash is a hierarchical digest of entire set
[Merkle]
7
x2
x1
x4
x3
x5
x7
x6
a
b
c
x8
12/7/2010
Data Integrity
Hash Tree Authentication
Assumptions
Collision resistant hash function
Root hash is known
Membership proof of an item
path from the item to the root (L/R sequence) plus hash values of sibling nodes
logarithmic size and verification time
Example
g = h(h(a, h(x3, x4)), d)
The proof of x4 is the sequence [(x3, L), (a , L), (d, R)]
8
x2
x1
x4
x3
x5
x7
x6
a
b
e
f
c
d
g
x8
12/7/2010
Data Integrity
Stream Authentication with Packet Losses
Sequence of plaintexts to be transmitted p1, p2 , …, pn
Build a hash tree on top of items (i, pi)
Transmit the signed root hash
For each item pi, transmit packet (i, pi, proof(i,pi))
Logarithmic space overhead and verification time per packet
Lost packets do not prevent authentication of future packets
Off-line scheme
9
12/7/2010
Data Integrity
introduction.pptx
Introduction to Computer Security (CS-353)
Session 1
‹#›/51
Hi everyone. My name is Mikhail I. Gofman. It’s Great to be here.
I will be presenting our work titled Preserving confidentiality in Virtual Machine Checkpointing and Role Based Access Control
1
Course Information
Course: CS-353-01 (3 credits)
Time: M-W-Th 6:00 – 9:00 PM
Place: CS104
Course Website: Titanium
Instructor: Mr. Heckathorn
Email: [email protected]
Office: CS-401
Office Hours:M-W-Th 4:45-5:45
‹#›/51
Prerequisites
Passing the Exam in Programming Proficiency or enrollment in CPSC 301, or have the permission of the CS department.
Failure to meet the prerequisites may result in you being dropped administratively.
Preserving Confidentiality in Virtual Machine Checkpointing and Role Based Access Control
‹#›/51
3
Course Objectives
Cyber attacks are growing in number and sophistication.
Consequences: privacy violations, financial losses, divulgence of national secrets, and much more.
Both public and private sectors need cybsersecurity-aware professionals.
Course Objectives: To learn about different kinds of cyber threats and countermeasures.
Topics Covered:
Physical Security
System Security
Malware
Cryptography
Network Security
Virtualization and Cloud Security
Web Security
Distributed Systems Security
Ethics
Others
‹#›/51
My talk will consist of 3 parts.
First, I will present a mechanism for protecting confidential information stored in the virtual machine checkpoints.
I will then present efficient algorithms for efficient analysis of Administrative Role Based Access Control policies.
Finally, I will conclude with a discussion of the future work.
4
Texts
Michael T. Goodrich and Roberto Tamassia, Introduction to Computer Security, ISBN-13: 978-0-321-51294-9, ISBN-10: 0-321-51294-4.
All additional materials shall be posted on Titanium.
‹#›/51
Assignments
Written assignments: may be done by groups of 2 students unless specified otherwise.
Note* Both names on the file, equal credit for both
Programming assignments:
To be done individually.
Must use Linux OS unless otherwise specified.
May use C, C++, Java, or C# (ask for other languages).
All completed assignments must be submitted via Email.
Late assignments shall be penalized 10% per day.
No assignment shall be accepted after 3 days from the deadline.
‹#›/51
Quizzes
In-Class quizzes:
Closed book.
Test your understanding of the material presented in class.
Missed quizzes shall earn a grade of 0 (unless you can provide written evidence of a legitimate excuse e.g. doctor’s note).
Take-home quizzes:
Require critical thinking (and creativity!).
Late submissions shall be penalized 10%.
No quiz shall be accepted after 24 hours from the deadline.
‹#›/51
Exams
Final exam is comprehensive and open book.
Final Exam: 5/27/2019 6-9 PM.
Missed exams shall be dealt with according to University policies on incompletes and withdrawals.
‹#›/51
Final Project
Can either be a written research project or a programming project.
The final projects may be done in groups of 3.
A list of topics shall be posted on Titanium.
No more than 2 groups shall be assigned the same topic.
Preserving Confidentiality in Virtual Machine Checkpointing and Role Based Access Control
‹#›/51
Attendance and Participation
The attendance is mandatory and shall be taken at beginning of every class.
Participate in class discussions (don’t be afraid!).
Ask questions!
Preserving Confidentiality in Virtual Machine Checkpointing and Role Based Access Control
‹#›/51
Extra Credit
Some assignments, projects, exams, and quizzes may include bonus sections.
No other forms of extra credit shall be granted.
Preserving Confidentiality in Virtual Machine Checkpointing and Role Based Access Control
‹#›/51
Asking Questions
Never be afraid to ask:
In class or after class.
During office hours.
Make Google your friend (can’t beat the availability and response time!)
‹#›/51
Class Cancellation Policy
All class cancellations shall be announced by email.
Instructor does not arrive within the first 15 minutes of class = class is canceled.
‹#›/51
Academic Honesty
Preserving Confidentiality in Virtual Machine Checkpointing and Role Based Access Control
‹#›/51
Academic Honesty
Incidents of cheating shall be treated with utmost seriousness.
You may discuss the problems with other students, however, you must write your own solutions.
Discussing solutions to the problem is NOT acceptable.
Copying an assignment from another student or allowing another student to copy your work may lead to an automatic F for this course.
If you have any questions about whether an act of collaboration may be treated as academic dishonesty, please consult the instructor before you collaborate.
Moss shall be used to detect plagiarism in programming assignments.
Preserving Confidentiality in Virtual Machine Checkpointing and Role Based Access Control
‹#›/51
Emergency Policy
Please familiarize yourself with the actions to take in case of an emergency.
The information can be found at http://prepare.fullerton.edu/
Preserving Confidentiality in Virtual Machine Checkpointing and Role Based Access Control
‹#›/51
Disabled Student Services
Information for students with disabilities can be found at: http://www.fullerton.edu/DSS/
Preserving Confidentiality in Virtual Machine Checkpointing and Role Based Access Control
‹#›/51
Course Syllabus
You are required to read the syllabus!
A copy of the syllabus is available on Titanium.
If something is not clear, ask the instructor.
Preserving Confidentiality in Virtual Machine Checkpointing and Role Based Access Control
‹#›/51
Fundamental Concepts
Goodrich Chapter 1
‹#›/51
19
My First Day at CSUF
‹#›/51
Why is cyber crime on the rise?
Systems with legacy features not designed for security.
Growth of the internet.
Complex systems with vulnerabilities.
Coping with cyber threats:
Sound models that:
Define the important security properties
Anticipate cyber threats
Incorporate defense mechanisms.
Sound implementations that are rigorously tested for security vulnerabilities.
Monitor deployed systems and quickly resolve any detected security breaches.
‹#›/51
What is Information Security?
Confidentiality, Integrity, Availability (C.I.A)
Confidentiality: avoidance of unauthorized disclosure of information.
Confidentiality can be provided through:
Encryption: transforming information such that the result cannot be read without the knowledge of some secret key.
Access Control: restricting access of information to only authorized individuals/systems.
Authentication: establishing the identity of the individual or system prior to granting access.
Physical Security: establish physical barriers that prevent access to the system.
‹#›/51
What is Information Security?
Confidentiality, Integrity, Availability (C.I.A).
Integrity: preventing information from being altered in unauthorized ways.
Backups: periodic archiving of data.
Checksum: a function that maps the contents of a file to a numerical value.
Slight changes in the file content trigger huge changes in the numerical value.
Data correcting codes: store data in such a way that changes can be easily detected and corrected.
Question: to protect integrity of a file, is it sufficient to simply protect the file content?
No! We also must protect file attributes
(e.g. file creator, owner, date created, etc)!
‹#›/51
What is Information Security?
Confidentiality, Integrity, Availability (C.I.A).
Availability: information is accessible and modifiable in a timely fashion by those authorized to do so.
Physical protections: infrastructure designed to keep information available in the presence of physical challenges.
Computational Redundancies: computers and storage devices that serve as fallback in case of failure.
‹#›/51
What is Information Security?
Assurance, Authenticity, Anonymity (A.A.A): a modern addition to the classical concepts of C.I.A.
Assurance: how the trust is provided and managed.
Policies: specify behavioral expectations that people and systems have for themselves and others.
Permissions: describe behaviors that are allowed by the agents that interact with a person or system.
Protections: mechanisms to enforce permissions and policies.
‹#›/51
Admittingly, trust is difficult to quantify. However, we know that it involves a degree to which we trust the system.
25
What is Information Security?
Assurance, Authenticity, Anonymity (A.A.A)
Authenticity: ability to determine that the statements made by people or systems are genuine:
Nonrepudiation: authentic statements cannot be denied. Can be achieved through digital signatures.
Digital Signature: a cryptographic computation based on the contents of the statement, that enables nonrepudiation.
Similar to the real-world, traditional signatures.
If the message contents change, so will their digital signature (unlike in traditional signature).
‹#›/51
What is Information Security?
Assurance, Authenticity, Anonymity (A.A.A)
Anonymity: certain records or transactions are not attributable to any specific individual.
Aggregation: combining information from many individuals e.g. through sums or averages that cannot be tied to a specific individual.
Mixing: intertwining of transactions, information, or communications in a way that cannot be traced to any individual.
Proxies: trusted agents that are willing to engage in actions for an individual in a way that cannot be traced back to that individual.
Pseudonyms: fictional identities used in real transactions.
‹#›/51
Types of Cyberatacks
Eavesdropping: unauthorized interception of information that was meant for someone else.
Alteration: unauthorized modification of information.
Example: the man in the middle attack: network stream is intercepted, modified, and retransmitted.
Denial-of-service (DoS): interruption or degradation of data service or information access.
Masquerading: the fabrication of information that is purported to be from someone who is not actually the author.
Repudiation: the denial or commitment of data receipt.
Correlation and traceback: integration of multiple data sources and information flows in order to obfuscate the source of information.
‹#›/51
Defending Against Attacks: Access Control
Restricts access of information to only authorized individuals/systems.
Protects confidentiality, integrity, and anonymity.
Different approaches:
Access control matrices
Access control lists (ACLs)
Capabilities
Role Based Access Control
Best practice: enforce the principle of least privilege: i.e. restrict access only to those who need it.
‹#›/51
Defending Against Attacks: Access Control
Access control matrix:
| /etc/passwd | /usr/bin | /u/roberto/ | /admin | |
| root | read,write | read,write, exec | read,write, exec | read,write,exec |
| mike | read | read,exec | ||
| roberto | read | read,exec | read,write, exec | |
| backup | read | read,exec | read,exec | read,exec |
| … | … | … | … | … |
‹#›/51
Defending Against Attacks: Access Control
Access control lists (ACLs):
/etc/passwd
/usr/bin
root: r,w
mike: r
roberto: r
backup: r
root: r,w,x
mike: r,x
roberto: r,x
backup: r,x
root: r,w,x
backup: r,x
root: r,w,x
backup: r,x
/admin/
/u/roberto
‹#›/51
Defending Against Attacks: Access Control
Access control lists in Linux (Demo):
Use the setfacl command to set permissions.
Use getfacl command to retrieve permissions.
Example: setfacl -m u:lisa:r file: grant user lisa permission to read file file.
Example: setfacl –x u:lisa file: revoke all permissions of user lisa on file file.
See https://access.redhat.com/site/documentation/en-US/Red_Hat_Enterprise_Linux/6/html/Storage_Administration_Guide/s1-acls-setting.html for more information.
Preserving Confidentiality in Virtual Machine Checkpointing and Role Based Access Control
‹#›/51
Defending Against Attacks: Access Control
Capabilities:
root
/etc/passwd: r,w,x;
/usr/bin: r,w,x;
/u/roberto: r,w,x
/admin/: r,w,x
mike
/etc/passwd: r,w,x;
/usr/bin: r,x
roberto
/etc/passwd: r;
/usr/bin: r;
/u/roberto r,x;
/admin/: r,x;
backup
/etc/passwd: r,x;
/usr/bin: r,x;
/u/roberto r,x;
/admin/: r,x;
‹#›/51
Defending Against Attacks: Access Control
Capabilities in Linux (Demo):
Permissions are associated with programs (unlike with users, as on the previous diagram).
Use setcap command to set up permissions.
Use getcap command to retrieve permissions.
Example: setcap cap_dac_override=ep /bin/cat: when accessing files, the process bypasses read, write, execute permission checks.
See http://man7.org/linux/man-pages/man7/capabilities.7.html for more information.
‹#›/51
Defending Against Attacks: Access Control
Role Based Access Control (RBAC): Users are assigned to roles and roles are associated with permissions.
A role is typically a job function or a position in an organization e.g. doctor, nurse, etc.
A user has a permission only if he is assigned to some role with that permission.
Examples:
Role Doctor has the permission to grant prescriptions: (Doctor, grantPrescriptions).
User Bob is assigned to role Doctor: (Bob,Doctor).
Hence, Bob has the permission to grant prescriptions.
Widely used in large organizations.
‹#›/51
Defending Against Attacks: Access Control
Systems that use RBAC:
Microsoft Active Directory
Microsoft SQL Server
SELinux
Grsecurity
FreeBSD
Solaris
Oracle DBMS
PostgreSQL 8.1
Wikipedia
Many others
Source: http://allcomputers.us/windows_server/exchange-server-2010---role-based-access-control.aspx
RBAC Policy Editor in MS Active Directory
‹#›/51
Defending Against Attacks: Access Control
Access Control Matrix vs RBAC Example: 1000 users where each user has 10 identical permissions:
Access control matrix: 1000 * 10 = 10,000 permission assignments!
RBAC: define role r and assign the 10 permissions to the role. Next, assign 1000 users to role r.
10 role-permission assignments + 1,000 user-role assignments = 1,010 assignments.
‹#›/51
Defending Against Attacks: Access Control
RBAC Role Hierarchy:
r1 r2: r1 inherits from r2, r1 is senior to r2.
Permission flows up, Membership flows down.
Every member of r1 is a member of r2.
Members of r1 have all the permissions that members of r2 have.
Faculty
TA
Univ-Employee
Student
Univ-Member
Assign grades
Assign homework scores
Receive health benefits
Register for Courses
Use gym
Bob is a Student
Alice is a TA
Jack is a faculty
‹#›/51
38
Defending Against Attacks: Access Control
RBAC Separation of Duty Constraints:
Prevent a single user from garnering too much authority.
Two types:
Static Separation of Duty (SSD)
Dynamic Separation of Duty (DSD)
‹#›/51
39
Defending Against Attacks: Access Control
SSD: constraints on assignment of user to role.
If user is member of one role, it gets no membership for other role.
(DeptChair, Dean) ∈ SSD
A user cannot be in both Deptchair and Dean roles
Constraints are inherited within role hierarchy.
(DeptChair, Dean) ∈ SSD, Provost Dean
(DeptChair, Provost) ∈ SSD
Example:
‹#›/51
40
Static separation of duty places constraint on assignment of users to roles. If (r1,r2) \in ssd, then if the user has been assigned to role r1, then the user cannot be assigned to r2. For example, we can specify that a user cannot be in both deptchair and dean roles as … Further, static separation of duty constraint can be inherited. For example, given this separate of duty constraint and the role hierarchy which specifies that role provost is senior to dean, then (..) is also a static separation of duty constraint.
Defending Against Attacks: Access Control
DSD: User cannot act simultaneously in both roles,
Cashier
Correct Error
Supervisor
Closes Cashier Role session
Opens Supv Role session
Accounting Error
(Supervisor, Cashier) ∈ DSD
A user cannot invoke both Supervisor and Cashier roles at the same time
Example:
‹#›/51
41
Defending Against Attacks: Cryptography
Encryption: enables two parties to establish confidential communications over an insecure channel.
Key idea: instead of transmitting the original message, transmit a ciphertext of the message.
Plaintext: the original message
Ciphertext: plaintext after transformation by an encryption algorithm.
Decryption algorithm: transforms ciphertext back into plaintext.
Example: Let P,C,E,D represent plaintext, ciphertext, encryption algorithm, and decryption algorithm respectively.
C = E(P)
P = D(C)
‹#›/51
Defending Against Attacks: Cryptography
Cryptosystem components:
The set of all possible plaintexts
The set of all possible ciphertexts
The set of keys encryption and decryption keys i.e. secret numbers or strings shared between the communicating parties:
Encryption key: used for encrypting the plaintext
Decryption key: used for deciphering the ciphertext
The correspondence between encryption and decryption keys.
The encryption/decryption algorithm.
‹#›/51
Defending Against Attacks: Cryptography
Types of cryptography:
Symmetric: the same key is used for encryption and decryption.
Public-key: each user has a public Pb and private key Pr.
The keys are mathematically linked: what is encrypted using Pb can be decrypted using Pr and vice-versa.
Same key cannot be used for both encryption and decryption.
‹#›/51
Defending Against Attacks: Cryptography
Symmetric vs Public-Key:
Public-key: easy to provide digital signatures:
encrypt the message Pr
publish Pb.
Anybody can verify the signature by checking if the message is decryptable using Pb.
Symmetric: in practice is faster than public-key.
We need both: use public-key cryptography to securely distribute the symmetric key and then use symmetric cryptography to encrypt all communications.
More details later in the course.
‹#›/51
Implementation and Usability Issues
Security solutions should not be in the way of usability:
Example: encrypting network communications should not prohibitively slow down the network.
Example: passwords should be easy to remember but hard to guess:
e.g. “Mark took Lisa to Disneyland on March 15” = MtLtDoM15 (or MtL+DoM15 since “t” looks like “+”).
‹#›/51
Acknowledgements
Some slides borrowed from Dr. Ping Yang at Binghamton University.
‹#›/51
Next Class
Physical Security (Goodrich Chapter 2).
‹#›/51
Ch09-SecureStorage.pptx
Secure Storage
1
Lost Laptops
Lost and stolen laptops are a common occurrence
Estimated occurrences in US airports every week: 12,000
Average cost of a lost laptop for a corporation is $50K
Costs include data breach, intellectual property loss, forensics, lost productivity, legal and regulatory expenses
Data breach much more serious than hardware loss
Encryption decreases cost by $20K
The existence of a full backup increases cost
Data breach cost estimated at $200 per customer record
Direct costs include discovery, notification and response
Indirect costs include customer turnover (higher loss and lower acquisition)
Data can also be copied while laptop is unattended
2
Ponemon Institute. Research Studies & White Papers: Security
Other Data Protection Scenarios
Defending against loss of USB drives and smart phones
Defending against data-stealing malware
Defending against equipment seizure
Donating decommissioned machines
Recycling obsolete or faulty machines
Off-site backups
Cloud storage
3
Password-Based File Encryption
Microsoft Office 97/2003
40-bit encryption key
Guaranteed cracking in two weeks with standard PC
Microsoft Office 2007
AES encryption
Default 128-bit key size can be increased to 256
Secret key derived from password by iteratively hashing salted password 50,000 times with SHA-1
Adobe Acrobat 9
AES encryption
256-bit keys
Secret key derived from password by hashing salted password once with SHA-256, which is faster than SHA-1 …
Elcomsoft markets password-recovery tools
Crack attempts per second: 5K Office 2007 vs. 75M for Acrobat 9
4
Encryption of File Systems
Disk encryption
Block-level encryption
Encryption of physical or logical drive
BitLocker in Windows Vista and 7
TrueCrypt open source software
File system encryption
File-level encryption
Encrypting File System (EFS) in Windows
5
Sharing Encrypted Files
Solution A
Encrypt file with symmetric key K
Share K with authorized users
Users need to keep many keys
User revocation requires redistributing new key
Solution B
Different symmetric keys K1, …, Kn for authorized users
Encrypt file multiple times with K1, …, Kn
Inefficient in terms of space and computing time
Solution C
Encrypt file with single symmetric key K
Encrypt K with public keys of authorized users PK1, …, PKn
Store with file EPK1(K), …, EPKn(K)
6
Encrypting File System (EFS)
Available in Windows since Windows 2000
Features
Work transparently by providing automatic encryption/decryption of files in specified folders
Protects file content but not file name and other metadata
Supports sharing of encrypted files
Keys unlocked on successful user login
Latest version uses RSA, SHA-256, and AES
Issues
Protection only local to file system
File copied to another file system is decrypted
Email attachment sent decrypted
File content may be leaked to unprotected temporary files
Key management is cumbersome
7
EFS Keys
Users have public-private key pairs
Each file is encrypted with a different symmetric file encryption key (FEK)
FEK is encrypted with public key of file owner and other authorized users
Data Decryption Fields (DDF) stored in file header (metadata)
ID of authorized user
FEK encrypted with public key of user
Data Recovery Fields (DRFs) provide additional encrypted FEKs, associated with recovery agents
8
EPK1(FEK)
ID1
EPK2(FEK)
ID2
EPK3(FEK)
ID3
EFEK(file contents)
Working with EFS
Initial encryption
File encrypted when created or EFS initialized
DDF of file owner created and added to file header
Adding new authorized user
DDF of new user created and added to file header
Any authorized user can add other users
Removing authorized user
DDF of revoked user removed from file header
File should be re-encrypted with new FEK, but is not …
9
BitLocker
Targets lost-laptop scenario
Encrypts NTFS volumes
All disk sectors encrypted with symmetric encryption method
Key can be provided by user at boot time
Passphrase
Hardware token
Key can be stored in special cryptographic chip that releases it after checking the integrity of the system
Trusted Platform Module (TPM)
10
BitLocker Architecture
Volumes
Small unencrypted boot volume
Large encrypted volume storing rest of OS and user files
Keys
Volume Master Key (VMK)
Unlocked through authentication procedure
Full Volume Encryption Key
Used to encrypt sectors of encrypted volume
Stored on boot volume encrypted with VMK
Kept in memory and never written unencrypted to disk
11
Encrypted Volume
Boot Volume
Startup and Operation
Authentication procedure checks integrity of system and unseals VMK
VMK used to decrypt FVEK, which is kept in main memory
For each disk sector accessed
Decrypt on read
Encrypt on write
12
Encrypting Disk Sectors
Each sector encrypted independently
Cannot create inter-sector dependencies
Speed is essential
Encryption and decryption at same or better rate than disk I/O peak rate in a standard laptop
Integrity checking not used
Sector sizes are powers of two (512B through 8,192B)
Adding a MAC would double space usage
Block ciphers are vulnerable to bit-flipping attacks in all known symmetric encryption modes
Plaintext of OS and applications code is predictable
Cryptographic design principles [Ferguson, 2006]
Encryption as poor man’s authentication
Preprocessing of each block to achieve diffusion
AES in CBC mode with sector-dependent IV
13
Trusted Platform Module (TPM)
Crypto processor
Mounted on motherboard
Tamper-resistant
Holds root key K that is never released
Has several platform configuration registers (PCRs), with fixed value at power up
Operation seal
Encrypts with K supplied plaintext p and associates it with a PCR i
Returns ciphertext c = EK(p) and MAC m = MAC(K,PCR[i])
Operation unseal
Input is a ciphertext c, PCR index i, and claimed MAC m
Decrypts ciphertext c and returns DK(c) if MAC(K,PCR[i]) = m
Operation extend
Only operation supported on PCRs
Input is a data item x and PCR index i
Computes step of hash chain: PCR[i] = h(PCR[i], x)
14
Image courtesy of sony.com
Booting with a TPM
Multi-level integrity checking
Allows BitLocker authentication without user intervention
Initialization
PCR extended with layers of trusted OS code (BIOS, boot loader, kernel, etc.)
Volume master key sealed to PCR
Trusted boot
Tamper-proof BIOS associated with TPM
Each code layer extends PCR with next layer
If integrity is not verified, PCR is extended with random value
Execution is transferred to next code layer
VMK can be unsealed only if the integrity of all layers has been successfully verified
15
Attacks on BitLocker
Compromise the TPM
Extraction of data from Infineon TPM recently presented by Christopher Tarnovsky at Black Hat DC 2010
Based on microprobing the substrate
Requires significant sophistication and specialized instruments
“Lest We Remember: Cold Boot Attacks on Encryption Keys”
Volume encryption key is stored in memory to decrypt the drive
RAM retains contents after power down for 2-3 seconds normally
Retention time can be extended for up to an hour by cooling the memory chip
Memory content accessed after booting from USB drive
Key recovered by analyzing memory
16
Image courtesy of Center for Information Technology Policy, Princeton University
Lost USB Drives
Millions of USB flash drives are in use today worldwide and thousands are lost each day, according to one estimate
Computer security does not prevent loss of USB drives
But we can try to avoid information leakage
17
Encrypting USB Flash Drives
In a perfect world, we would not store sensitive data on portable devices
All sensitive data should be held on secure servers.
Unfortunately, this approach is not always practical.
Design goals for data encryption on portable devices
Run on the device only
Not require host installation
Compatible with different platforms and file systems
Work from a nonprivileged account
Fast and possibly free …
18
TrueCrypt
Free open-source disk encryption software for Windows 7/Vista/XP, Mac OS X, and Linux
Creates an encrypted area (virtual encrypted disk) inside an ordinary file
In Windows, when the user provides the correct password, the file becomes a volume in My Computer with a drive letter—just like inserting a USB drive
Files copied to/from this encrypted volume are encrypted/decrypted on the fly, automatically and transparently
19
Create an encrypted volume on a usb flash drive
DEMO 1
20
Laptop Seizure and Deniability
Laptops and other electronic devices may be inspected, and even seized by police officers and other government personnel
Usually requires a warrant from a judge
A notable exception is the broad search and seizure authority granted to US customs
Scenario described in [Defeating Encrypted and Deniable File Systems, Czekis et al., 2006]
Alice is a human-rights worker who has sensitive information on her laptop
She uses TrueCrypt but she is concerned that the secret police will seize her computer and ask her to reveal the decryption key
She needs to protect her data in such a way that her encrypted files are deniable: nothing should reveal to the secret police that there are hidden files on her computer
21
Plausible Deniability
Political doctrine developed in the US in the 50's
If illegal operations are discovered, it should be possible to deny any connection or guilt of the principals
Applied to CIA operations. (i.e., Bay of Pigs failed invasion of Cuba)
In general, plausible deniability refers to
Any act that leaves little or no evidence of irregularities or abuse
In computer parlance, it is the ability to deny the presence of data hidden within a container
22
TrueCrypt Hidden Volume
Padded with random bits
23
TrueCrypt Hidden Volume
Padded with random bits
Inside the standard TrueCrypt volume are still random bits
24
TrueCrypt Hidden Volume
Padded with random bits
Inside the standard TrueCrypt volume are still random bits
Password (PA) standard volume
Password (PB) hidden volume
PA ≠ PB
25
Create a Hidden volume on a usb flash drive
DEMO 2
26
Ch08-CryptoConcepts.pptx
Cryptography
12/1/2010
1
Cryptography
Symmetric Cryptosystem
Scenario
Alice wants to send a message (plaintext P) to Bob.
The communication channel is insecure and can be eavesdropped
If Alice and Bob have previously agreed on a symmetric encryption scheme and a secret key K, the message can be sent encrypted (ciphertext C)
Issues
What is a good symmetric encryption scheme?
What is the complexity of encrypting/decrypting?
What is the size of the ciphertext, relative to the plaintext?
12/1/2010
Cryptography
2
C
P
P
encrypt
K
decrypt
K
Basics
Notation
Secret key K
Encryption function EK(P)
Decryption function DK(C)
Plaintext length typically the same as ciphertext length
Encryption and decryption are permutation functions (bijections) on the set of all n-bit arrays
Efficiency
functions EK and DK should have efficient algorithms
Consistency
Decrypting the ciphertext yields the plaintext
DK(EK(P)) = P
12/1/2010
Cryptography
3
Attacks
Attacker may have
collection of ciphertexts (ciphertext only attack)
collection of plaintext/ciphertext pairs (known plaintext attack)
collection of plaintext/ciphertext pairs for plaintexts selected by the attacker (chosen plaintext attack)
collection of plaintext/ciphertext pairs for ciphertexts selected by the attacker (chosen ciphertext attack)
12/1/2010
Cryptography
4
Hi, Bob.
Don’t invite Eve to the party!
Love, Alice
Encryption
Algorithm
Plaintext
Ciphertext
key
Eve
Hi, Bob.
Don’t invite Eve to the party!
Love, Alice
Plaintext
Ciphertext
key
ABCDEFG
HIJKLMNO
PQRSTUV
WXYZ.
Plaintext
Ciphertext
key
IJCGA, CAN DO HIFFA GOT TIME.
Plaintext
Ciphertext
key
Eve
001101
110111
(a)
(b)
(c)
(d)
Eve
Eve
Eve
Encryption
Algorithm
Encryption
Algorithm
Encryption
Algorithm
Brute-Force Attack
Try all possible keys K and determine if DK(C) is a likely plaintext
Requires some knowledge of the structure of the plaintext (e.g., PDF file or email message)
Key should be a sufficiently long random value to make exhaustive search attacks unfeasible
12/1/2010
Cryptography
5
Image by Michael Cote from http://commons.wikimedia.org/wiki/File:Bingo_cards.jpg
Encrypting English Text
12/1/2010
Cryptography
6
English text typically represented with 8-bit ASCII encoding
A message with t characters corresponds to an n-bit array, with n = 8t
Redundancy due to repeated words and patterns
E.g., “th”, “ing”
English plaintexts are a very small subset of all n-bit arrays
Ciphertexts n-bit strings
Plaintexts n-bit strings
English text
Ciphertext of English text
Entropy of Natural Language
12/1/2010
Cryptography
7
Information content (entropy) of English: 1.25 bits per character
t-character arrays that are English text:
(21.25)t = 21.25 t
n-bit arrays that are English text:
21.25 n/8 20.16 n
For a natural language, constant a < 1 such that there are 2an messages among all n-bit arrays
Fraction (probability) of valid messages
2an / 2n = 1 / 2(1-a)n
Brute-force decryption
Try all possible 2k decryption keys
Stop when valid plaintext recognized
Given a ciphertext, there are 2k possible plaintexts
Expected number of valid plaintexts
2k / 2(1-a)n
Expected unique valid plaintext , (no spurious keys) achieved at unicity distance
n = k / (1-a)
For English text and 256-bit keys, unicity distance is 304 bits
Substitution Ciphers
12/1/2010
Cryptography
8
Each letter is uniquely replaced by another.
There are 26! possible substitution ciphers.
There are more than 4.03 x 1026 such ciphers.
One popular substitution “cipher” for some Internet posts is ROT13.
Public domain image from http://en.wikipedia.org/wiki/File:ROT13.png
Frequency Analysis
12/1/2010
Cryptography
9
Letters in a natural language, like English, are not uniformly distributed.
Knowledge of letter frequencies, including pairs and triples can be used in cryptologic attacks against substitution ciphers.
Substitution Boxes
Substitution can also be done on binary numbers.
Such substitutions are usually described by substitution boxes, or S-boxes.
12/1/2010
Cryptography
10
One-Time Pads
There is one type of substitution cipher that is absolutely unbreakable.
The one-time pad was invented in 1917 by Joseph Mauborgne and Gilbert Vernam
We use a block of shift keys, (k1, k2, . . . , kn), to encrypt a plaintext, M, of length n, with each shift key being chosen uniformly at random.
Since each shift is random, every ciphertext is equally likely for any plaintext.
12/1/2010
Cryptography
11
Weaknesses of the One-Time Pad
In spite of their perfect security, one-time pads have some weaknesses
The key has to be as long as the plaintext
Keys can never be reused
Repeated use of one-time pads allowed the U.S. to break some of the communications of Soviet spies during the Cold War.
12/1/2010
Cryptography
12
Public domain declassified government image from
https://www.cia.gov/library/center-for-the-study-of-intelligence/csi-publications/books-and-monographs/venona-soviet-espionage-and-the-american-response-1939-1957/part2.htm
Block Ciphers
In a block cipher:
Plaintext and ciphertext have fixed length b (e.g., 128 bits)
A plaintext of length n is partitioned into a sequence of m blocks, P[0], …, P[m1], where n bm n + b
Each message is divided into a sequence of blocks and encrypted or decrypted in terms of its blocks.
12/1/2010
Cryptography
13
Plaintext
Blocks of
plaintext
Requires padding
with extra bits.
Padding
Block ciphers require the length n of the plaintext to be a multiple of the block size b
Padding the last block needs to be unambiguous (cannot just add zeroes)
When the block size and plaintext length are a multiple of 8, a common padding method (PKCS5) is a sequence of identical bytes, each indicating the length (in bytes) of the padding
Example for b = 128 (16 bytes)
Plaintext: “Roberto” (7 bytes)
Padded plaintext: “Roberto999999999” (16 bytes), where 9 denotes the number and not the character
We need to always pad the last block, which may consist only of padding
12/1/2010
Cryptography
14
Block Ciphers in Practice
Data Encryption Standard (DES)
Developed by IBM and adopted by NIST in 1977
64-bit blocks and 56-bit keys
Small key space makes exhaustive search attack feasible since late 90s
Triple DES (3DES)
Nested application of DES with three different keys KA, KB, and KC
Effective key length is 168 bits, making exhaustive search attacks unfeasible
C = EKC(DKB(EKA(P))); P = DKA(EKB(DKC(C)))
Equivalent to DES when KA=KB=KC (backward compatible)
Advanced Encryption Standard (AES)
Selected by NIST in 2001 through open international competition and public discussion
128-bit blocks and several possible key lengths: 128, 192 and 256 bits
Exhaustive search attack not currently possible
AES-256 is the symmetric encryption algorithm of choice
12/1/2010
Cryptography
15
The Advanced Encryption Standard (AES)
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 to five finalists, and ultimately chose an algorithm that is now known as the Advanced Encryption Standard (AES).
AES is a block cipher that operates on 128-bit blocks. It is designed to be used with keys that are 128, 192, or 256 bits long, yielding ciphers known as AES-128, AES-192, and AES-256.
12/1/2010
Cryptography
16
AES Round Structure
The 128-bit version of the AES encryption algorithm proceeds in ten rounds.
Each round performs an invertible transformation on a 128-bit array, called state.
The initial state X0 is the XOR of the plaintext P with the key K:
X0 = P XOR K.
Round i (i = 1, …, 10) receives state Xi-1 as input and produces state Xi.
The ciphertext C is the output of the final round: C = X10.
12/1/2010
Cryptography
17
AES Rounds
Each round is built from four basic steps:
SubBytes step: an S-box substitution step
ShiftRows step: a permutation step
MixColumns step: a matrix multiplication step
AddRoundKey step: an XOR step with a round key derived from the 128-bit encryption key
12/1/2010
Cryptography
18
Block Cipher Modes
A block cipher mode describes the way a block cipher encrypts and decrypts a sequence of message blocks.
Electronic Code Book (ECB) Mode (is the simplest):
Block P[i] encrypted into ciphertext block C[i] = EK(P[i])
Block C[i] decrypted into plaintext block M[i] = DK(C[i])
12/1/2010
Cryptography
19
Public domain images from http://en.wikipedia.org/wiki/File:Ecb_encryption.png and http://en.wikipedia.org/wiki/File:Ecb_decryption.png
Strengths and Weaknesses of ECB
12/1/2010
Cryptography
20
Strengths:
Is very simple
Allows for parallel encryptions of the blocks of a plaintext
Can tolerate the loss or damage of a block
Weakness:
Documents and images are not suitable for ECB encryption since patters in the plaintext are repeated in the ciphertext:
Cipher Block Chaining (CBC) Mode
In Cipher Block Chaining (CBC) Mode
The previous ciphertext block is combined with the current plaintext block C[i] = EK (C[i 1] P[i])
C[1] = V, a random block separately transmitted encrypted (known as the initialization vector)
Decryption: P[i] = C[i 1] DK (C[i])
12/1/2010
Cryptography
21
DK
P[0]
DK
P[1]
DK
P[2]
DK
P[3]
V
C[0]
C[1]
C[2]
C[3]
EK
P[0]
EK
P[1]
EK
P[2]
EK
P[3]
V
C[0]
C[1]
C[2]
C[3]
CBC Encryption:
CBC Decryption:
Strengths and Weaknesses of CBC
12/1/2010
Cryptography
22
Weaknesses:
CBC requires the reliable transmission of all the blocks sequentially
CBC is not suitable for applications that allow packet losses (e.g., music and video streaming)
Strengths:
Doesn’t show patterns in the plaintext
Is the most common mode
Is fast and relatively simple
Java AES Encryption Example
Source
http://java.sun.com/javase/6/docs/technotes/guides/security/crypto/CryptoSpec.html
Generate an AES key
KeyGenerator keygen = KeyGenerator.getInstance("AES"); SecretKey aesKey = keygen.generateKey();
Create a cipher object for AES in ECB mode and PKCS5 padding
Cipher aesCipher; aesCipher = Cipher.getInstance("AES/ECB/PKCS5Padding");
Encrypt
aesCipher.init(Cipher.ENCRYPT_MODE, aesKey); byte[] plaintext = "My secret message".getBytes(); byte[] ciphertext = aesCipher.doFinal(plaintext);
Decrypt
aesCipher.init(Cipher.DECRYPT_MODE, aesKey); byte[] plaintext1 = aesCipher.doFinal(ciphertext);
12/1/2010
Cryptography
23
Stream Cipher
Key stream
Pseudo-random sequence of bits S = S[0], S[1], S[2], …
Can be generated on-line one bit (or byte) at the time
Stream cipher
XOR the plaintext with the key stream C[i] = S[i] P[i]
Suitable for plaintext of arbitrary length generated on the fly, e.g., media stream
Synchronous stream cipher
Key stream obtained only from the secret key K
Works for unreliable channels if plaintext has packets with sequence numbers
Self-synchronizing stream cipher
Key stream obtained from the secret key and q previous ciphertexts
Lost packets cause a delay of q steps before decryption resumes
12/1/2010
Cryptography
24
Key Stream Generation
RC4
Designed in 1987 by Ron Rivest for RSA Security
Trade secret until 1994
Uses keys with up to 2,048 bits
Simple algorithm
Block cipher in counter mode (CTR)
Use a block cipher with block size b
The secret key is a pair (K,t), where K a is key and t (counter) is a b-bit value
The key stream is the concatenation of ciphertexts
EK (t), EK (t + 1), EK (t + 2), …
Can use a shorter counter concatenated with a random value
Synchronous stream cipher
12/1/2010
Cryptography
25
Attacks on Stream Ciphers
Repetition attack
if key stream reused, attacker obtains XOR of two plaintexts
Insertion attack [Bayer Metzger, TODS 1976]
retransmission of the plaintext with
a chosen byte inserted by attacker
using the same key stream
e.g., email message resent with new message number
12/1/2010
Cryptography
26
| P | P[i] | P[i+1] | P[i+2] | P[i+3] |
| S | S[i] | S[i+1] | S[i+2] | S[i+3] |
| C | C[i] | C[i+1] | C[i+2] | C[i+3] |
| P | P[i] | X | P[i+1] | P[i+2] |
| S | S[i] | S[i+1] | S[i+2] | S[i+3] |
| C | C[i] | C[i+1] | C[i+2] | C[i+3] |
Original
Retransmission
Public Key Encryption
12/1/2010
27
Cryptography
Facts About Numbers
Prime number p:
p is an integer
p 2
The only divisors of p are 1 and p
Examples
2, 7, 19 are primes
-3, 0, 1, 6 are not primes
Prime decomposition of a positive integer n:
n = p1e1 … pkek
Example:
200 = 23 52
Fundamental Theorem of Arithmetic
The prime decomposition of a positive integer is unique
12/1/2010
Cryptography
28
Greatest Common Divisor
The greatest common divisor (GCD) of two positive integers a and b, denoted gcd(a, b), is the largest positive integer that divides both a and b
The above definition is extended to arbitrary integers
Examples:
gcd(18, 30) = 6 gcd(0, 20) = 20 gcd(-21, 49) = 7
Two integers a and b are said to be relatively prime if
gcd(a, b) = 1
Example:
Integers 15 and 28 are relatively prime
12/1/2010
Cryptography
29
Modular Arithmetic
Modulo operator for a positive integer n
r = a mod n
equivalent to
a = r + kn
and
r = a - a/n n
Example:
29 mod 13 = 3 13 mod 13 = 0 -1 mod 13 = 12
29 = 3 + 213 13 = 0 + 113 12 = -1 + 113
Modulo and GCD:
gcd(a, b) = gcd(b, a mod b)
Example:
gcd(21, 12) = 3 gcd(12, 21 mod 12) = gcd(12, 9) = 3
12/1/2010
Cryptography
30
Euclid’s GCD Algorithm
Euclid’s algorithm for computing the GCD repeatedly applies the formula
gcd(a, b) = gcd(b, a mod b)
Example
gcd(412, 260) = 4
12/1/2010
Cryptography
31
| a | 412 | 260 | 152 | 108 | 44 | 20 | 4 |
| b | 260 | 152 | 108 | 44 | 20 | 4 | 0 |
Algorithm EuclidGCD(a, b)
Input integers a and b
Output gcd(a, b)
if b = 0
return a
else
return EuclidGCD(b, a mod b)
Analysis
Let ai and bi be the arguments of the i-th recursive call of algorithm EuclidGCD
We have
ai + 2 = bi + 1 = ai mod ai + 1 < ai + 1
Sequence a1, a2, …, an decreases exponentially, namely
ai + 2 ½ ai for i > 1
Case 1 ai + 1 ½ ai ai + 2 < ai + 1 ½ ai
Case 2 ai + 1 > ½ ai ai + 2 = ai mod ai + 1 = ai - ai + 1 ½ ai
Thus, the maximum number of recursive calls of algorithm EuclidGCD(a. b) is
1 + 2 log max(a. b)
Algorithm EuclidGCD(a, b) executes O(log max(a, b)) arithmetic operations
The running time can also be expressed as O(log min(a, b))
12/1/2010
Cryptography
32
Multiplicative Inverses (1)
The residues modulo a positive integer n are the set
Zn = {0, 1, 2, …, (n - 1)}
Let x and y be two elements of Zn such that
xy mod n = 1
We say that y is the multiplicative inverse of x in Zn and we write y = x-1
Example:
Multiplicative inverses of the residues modulo 11
12/1/2010
Cryptography
33
| x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| x-1 | 1 | 6 | 4 | 3 | 9 | 2 | 8 | 7 | 5 | 10 |
Multiplicative Inverses (2)
Theorem
An element x of Zn has a multiplicative inverse if and only if x and n are relatively prime
Example
The elements of Z10 with a multiplicative inverse are 1, 3, 7, 9
Corollary
If is p is prime, every nonzero residue in Zp has a multiplicative inverse
Theorem
A variation of Euclid’s GCD algorithm computes the multiplicative inverse of an element x of Zn or determines that it does not exist
12/1/2010
Cryptography
34
| x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| x-1 | 1 | 7 | 3 | 9 |
Example: Measuring Lengths
Consider a stick of length a and a stick of length b such that a and b are relatively prime
Given two integers i and j, we can measure length n = ia + jb
We show that any integer n can be written as n = ia + jb for some integers i and j
Let s be the inverse of a in Zb We have sa mod b = 1
There exists integer t such that sa + tb = 1
Pick i = ns and j = nt
Thus, given two sticks of relatively prime integer lengths, we can measure any integer length
Example, measure length 2 with sticks of length 3 and 7
12/1/2010
Cryptography
35
3
7
3
3
7
3
Example: Double Hashing
Consider a hash table whose size n is a prime
In open addressing with double hashing, an operation on key x probes the following locations modulo n
i, i + d, i + 2d, i + 3d, …, i + (n – 1)d
where i = h1(x) and d = h2(x)
We show that each table location is probed by this sequence once
Suppose (i + jd) mod n = (i + kd) mod n for some integers j and k in the range [0, n – 1]
We have (j - k)d mod n = 0
Since n is prime, we have that n and d are relatively prime
Thus, d has an inverse d- 1 in Zn
Multiplying each side by d- 1, we obtain (j - k) mod n = 0
We conclude that j = k
12/1/2010
Cryptography
36
Powers
Let p be a prime
The sequences of successive powers of the elements of Zp exhibit repeating subsequences
The sizes of the repeating subsequences and the number of their repetitions are the divisors of p - 1
Example (p = 7)
12/1/2010
Cryptography
37
| x | x2 | x3 | x4 | x5 | x6 |
| 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 4 | 1 | 2 | 4 | 1 |
| 3 | 2 | 6 | 4 | 5 | 1 |
| 4 | 2 | 1 | 4 | 2 | 1 |
| 5 | 4 | 6 | 2 | 3 | 1 |
| 6 | 1 | 6 | 1 | 6 | 1 |
Fermat’s Little Theorem
Theorem
Let p be a prime. For each nonzero residue x of Zp, we have xp - 1 mod p = 1
Example (p = 5):
14 mod 5 = 1 24 mod 5 = 16 mod 5 = 1
34 mod 5 = 81 mod 5 = 1 44 mod 5 = 256 mod 5 = 1
Corollary
Let p be a prime. For each nonzero residue x of Zp, the multiplicative inverse of x is xp - 2 mod p
Proof
x(xp - 2 mod p) mod p = xxp - 2 mod p = xp - 1 mod p = 1
12/1/2010
Cryptography
38
Euler’s Theorem
The multiplicative group for Zn, denoted with Z*n, is the subset of elements of Zn relatively prime with n
The totient function of n, denoted with f(n), is the size of Z*n
Example
Z*10 = { 1, 3, 7, 9 } f(10) = 4
If p is prime, we have
Z*p = {1, 2, …, (p - 1)} f(p) = p - 1
Euler’s Theorem
For each element x of Z*n, we have xf(n) mod n = 1
Example (n = 10)
3f(10) mod 10 = 34 mod 10 = 81 mod 10 = 1
7f(10) mod 10 = 74 mod 10 = 2401 mod 10 = 1
9f(10) mod 10 = 94 mod 10 = 6561 mod 10 = 1
12/1/2010
Cryptography
39
RSA Cryptosystem
12/1/2010
Cryptography
40
Setup:
n = pq, with p and q primes
e relatively prime to f(n) = (p - 1) (q - 1)
d inverse of e in Zf(n)
Keys:
Public key: KE = (n, e)
Private key: KD = d
Encryption:
Plaintext M in Zn
C = Me mod n
Decryption:
M = Cd mod n
Example
Setup:
p = 7, q = 17
n = 717 = 119
f(n) = 616 = 96
e = 5
d = 77
Keys:
public key: (119, 5)
private key: 77
Encryption:
M = 19
C = 195 mod 119 = 66
Decryption:
C = 6677 mod 119 = 19
Complete RSA Example
Setup:
p = 5, q = 11
n = 511 = 55
f(n) = 410 = 40
e = 3
d = 27 (327 = 81 = 240 + 1)
12/1/2010
Cryptography
41
Encryption
C = M3 mod 55
Decryption
M = C27 mod 55
Security
Security of RSA based on difficulty of factoring
Widely believed
Best known algorithm takes exponential time
RSA Security factoring challenge (discontinued)
In 1999, 512-bit challenge factored in 4 months using 35.7 CPU-years
160 175-400 MHz SGI and Sun
8 250 MHz SGI Origin
120 300-450 MHz Pentium II
4 500 MHz Digital/Compaq
In 2005, a team of researchers factored the RSA-640 challenge number using 30 2.2GHz CPU years
In 2004, the prize for factoring RSA-2048 was $200,000
Current practice is 2,048-bit keys
Estimated resources needed to factor a number within one year
12/1/2010
Cryptography
42
| Length (bits) | PCs | Memory |
| 430 | 1 | 128MB |
| 760 | 215,000 | 4GB |
| 1,020 | 342106 | 170GB |
| 1,620 | 1.61015 | 120TB |
Correctness
We show the correctness of the RSA cryptosystem for the case when the plaintext M does not divide n
Namely, we show that
(Me)d mod n = M
Since ed mod f(n) = 1, there is an integer k such that
ed = kf(n) + 1
Since M does not divide n, by Euler’s theorem we have
Mf(n) mod n = 1
Thus, we obtain
(Me)d mod n =
Med mod n =
Mkf(n) + 1 mod n = MMkf(n) mod n =
M (Mf(n))k mod n =
M (Mf(n) mod n)k mod n =
M (1)k mod n =
M mod n =
M
Proof of correctness can be extended to the case when the plaintext M divides n
12/1/2010
Cryptography
43
Algorithmic Issues
The implementation of the RSA cryptosystem requires various algorithms
Overall
Representation of integers of arbitrarily large size and arithmetic operations on them
Encryption
Modular power
Decryption
Modular power
Setup
Generation of random numbers with a given number of bits (to generate candidates p and q)
Primality testing (to check that candidates p and q are prime)
Computation of the GCD (to verify that e and f(n) are relatively prime)
Computation of the multiplicative inverse (to compute d from e)
12/1/2010
Cryptography
44
Modular Power
The repeated squaring algorithm speeds up the computation of a modular power ap mod n
Write the exponent p in binary
p = pb - 1 pb - 2 … p1 p0
Start with
Q1 = apb - 1 mod n
Repeatedly compute
Qi = ((Qi - 1)2 mod n)apb - i mod n
We obtain
Qb = ap mod n
The repeated squaring algorithm performs O (log p) arithmetic operations
Example
318 mod 19 (18 = 10010)
Q1 = 31 mod 19 = 3
Q2 = (32 mod 19)30 mod 19 = 9
Q3 = (92 mod 19)30 mod 19 = 81 mod 19 = 5
Q4 = (52 mod 19)31 mod 19 = (25 mod 19)3 mod 19 = 18 mod 19 = 18
Q5 = (182 mod 19)30 mod 19 = (324 mod 19) mod 19 = 1719 + 1 mod 19 = 1
12/1/2010
Cryptography
45
| p5 - i | 1 | 0 | 0 | 1 | 0 |
| 2p5 - i | 3 | 1 | 1 | 3 | 1 |
| Qi | 3 | 9 | 5 | 18 | 1 |
Modular Inverse
Theorem
Given positive integers a and b, let d be the smallest positive integer such that
d = ia + jb
for some integers i and j.
We have
d = gcd(a,b)
Example
a = 21
b = 15
d = 3
i = 3, j = -4
3 = 321 + (-4)15 = 63 - 60 = 3
Given positive integers a and b, the extended Euclid’s algorithm computes a triplet (d,i,j) such that
d = gcd(a,b)
d = ia + jb
To test the existence of and compute the inverse of x Zn, we execute the extended Euclid’s algorithm on the input pair (x,n)
Let (d,i,j) be the triplet returned
d = ix + jn
Case 1: d = 1
i is the inverse of x in Zn
Case 2: d > 1
x has no inverse in Zn
12/1/2010
Cryptography
46
Pseudoprimality Testing
The number of primes less than or equal to n is about n / ln n
Thus, we expect to find a prime among O(b) randomly generated numbers with b bits each
Testing whether a number is prime (primality testing) is a difficult problem, though polynomial-time algorithms exist
An integer n 2 is said to be a base-x pseudoprime if
xn - 1 mod n = 1 (Fermat’s little theorem)
Composite base-x pseudoprimes are rare:
A random 100-bit integer is a composite base-2 pseudoprime with probability less than 10-13
The smallest composite base-2 pseudoprime is 341
Base-x pseudoprimality testing for an integer n:
Check whether xn - 1 mod n = 1
Can be performed efficiently with the repeated squaring algorithm
12/1/2010
Cryptography
47
Randomized Primality Testing
Compositeness witness function witness(x, n) with error probability q for a random variable x
Case 1: n is prime
witness(x, n) = false always
Case 2: n is composite
witness(x, n) = true in most cases, false with small probability q < 1
Algorithm RandPrimeTest tests whether n is prime by repeatedly evaluating witness(x, n)
A variation of base- x pseudoprimality provides a suitable compositeness witness function for randomized primality testing (Rabin-Miller algorithm)
12/1/2010
Cryptography
48
Algorithm RandPrimeTest(n, k)
Input integer n,confidence parameter k and composite witness function witness(x,n) with error probability q
Output an indication of whether n is composite or prime with probability 2-k
t k/log2(1/q)
for i 1 to t
x random()
if witness(x, n) = true
return “n is composite”
return “n is prime”
Cryptographic Hash Functions
12/1/2010
49
Cryptography
Hash Functions
A hash function h maps a plaintext x to a fixed-length value x = h(P) called hash value or digest of P
A collision is a pair of plaintexts P and Q that map to the same hash value, h(P) = h(Q)
Collisions are unavoidable
For efficiency, the computation of the hash function should take time proportional to the length of the input plaintext
Hash table
Search data structure based on storing items in locations associated with their hash value
Chaining or open addressing deal with collisions
Domain of hash values proportional to the expected number of items to be stored
The hash function should spread plaintexts uniformly over the possible hash values to achieve constant expected search time
12/1/2010
Cryptography
50
Cryptographic Hash Functions
A cryptographic hash function satisfies additional properties
Preimage resistance (aka one-way)
Given a hash value x, it is hard to find a plaintext P such that h(P) = x
Second preimage resistance (aka weak collision resistance)
Given a plaintext P, it is hard to find a plaintext Q such that h(Q) = h(P)
Collision resistance (aka strong collision resistance)
It is hard to find a pair of plaintexts P and Q such that h(Q) = h(P)
Collision resistance implies second preimage resistance
Hash values of at least 256 bits recommended to defend against brute-force attacks
A random oracle is a theoretical model for a cryptographic hash function from a finite input domain P to a finite output domain X
Pick randomly and uniformly a function h: P X over all possible such functions
Provide only oracle access to h: one can obtain hash values for given plaintexts, but no other information about the function h itself
12/1/2010
Cryptography
51
Birthday Attack
The brute-force birthday attack aims at finding a collision for a hash function h
Randomly generate a sequence of plaintexts X1, X2, X3,…
For each Xi compute yi = h(Xi) and test whether yi = yj for some j < i
Stop as soon as a collision has been found
If there are m possible hash values, the probability that the i-th plaintext does not collide with any of the previous i -1 plaintexts is 1 - (i - 1)/m
The probability Fk that the attack fails (no collisions) after k plaintexts is
Fk = (1 - 1/m) (1 - 2/m) (1 - 3/m) … (1 - (k - 1)/m)
Using the standard approximation 1 - x e-x
Fk e-(1/m + 2/m + 3/m + … + (k-1)/m) = e-k(k-1)/2m
The attack succeeds/fails with probability ½ when Fk = ½ , that is,
e-k(k-1)/2m = ½
k 1.17 m½
We conclude that a hash function with b-bit values provides about b/2 bits of security
12/1/2010
Cryptography
52