Computer Science- Dictionary Attack with and without Password Salt program
OS Security II
1
10/4/20
Introduction
Objective
State the functions of memory and file system security
Understand application program security including the concept and mechanism of buffer overflow attacks
In the last lecture, we talked about the basic concept of operating systems with the main components in computing systems.
And then we also talked about the functions for monitoring and protecting the processes.
In this lecture, we are going to talk about the functions for memory and file system security.
And then we will talk about the application program security including buffer overflow attacks.
Introduction
10/4/20
2
Memory and File system Security
The contents of a computer are encapsulated in its memory and file system.
Thus, protection of a computer’s content has to start with the protection of its memory and its file system.
So let’s talk about memory and file system security.
We already learned a set of main components in a computing system, which includes memory and file system.
For memory and file system security, we are going to talk about password-based authentication, access control models and access control list, and more about file permissions.
3
Password Security
The basic approach to guessing passwords from the password file is to conduct a dictionary attack, where each word in a dictionary is hashed and the resulting value is compared with the hashed passwords stored in the password file.
A dictionary of 500,000 “words” is often enough to discover most passwords.
The dictionary attack is a well-known approach to guess passwords.
And a dictionary of 500,000 “words” is often enough to break most passwords.
In that case, if we can test 1,000 passwords in a second, it takes only 500 seconds (or less than 10 minutes) to test the entire words in the dictionary.
Obviously we don’t want this to happen.
We want to make it hard to break the password even if it comes from a word in the dictionary.
4
Password Salt
One way to make the dictionary attack more difficult to launch is to use salt.
Associate a random number with each userid.
Rather than comparing the hash of an entered password with a stored hash of a password, the system compares the hash of an entered password and the salt for the associated userid with a stored hash of the password and salt.
Password salting is a technique to make the dictionary attack more difficult by adding some random number to the password.
5
How Password Salt Works
Without salt:
With salt:
1. User types userid, X, and password, P.
2. System looks up H, the stored hash of X’s password.
3. System tests whether h(P) = H.
1. User types userid, X, and password, P.
2. System looks up S and H, where S is the random salt for userid X and H is stored hash of S and X’s password.
3. System tests whether h(S||P) = H’.
…
X: H
…
Password file:
…
X: H’
…
Password file:
In the old mechanism, there was no concept of salting.
Now, let’s talk about how authentication takes place in the system without the use of salting.
When a new user is added to the system, the user sets up a new password.
Then the system makes a new entry in the password file for this new user.
But for greater security, the plaintext of password is not kept in the system.
Instead, the hashed result of the password is stored in the password file.
In the figure, we can see the hashed password H is stored for user ID 'X' in the password file.
Later, the user gives the user ID and password to get into the system.
Then the system computes the hash with the password given by the user, and if the hashed result is the same as the one in the password file for that user, the authentication is done successfully and the user can get into the system.
To hack the password, how many trials the attacker needs in case of dictionary attack?
It is 500,000 times, which takes less than 10 minutes to finish.
6
How Password Salt Works
Without salt:
With salt:
1. User types userid, X, and password, P.
2. System looks up H, the stored hash of X’s password.
3. System tests whether h(P) = H.
1. User types userid, X, and password, P.
2. System looks up S and H, where S is the random salt for userid X and H is stored hash of S and X’s password.
3. System tests whether h(S||P) = H’.
…
X: H
…
Password file:
…
X: H’
…
Password file:
With the salting technique, the system uses a long random number, also known as a salt, in addition to the password.
And the extended password with the random number is being hashed and stored in the password file.
With the salt, the length of the password increases, which makes the attacker to hack the password much more difficult.
7
How Salt Increases Search Space Size
Assuming that an attacker cannot find the salt associated with a userid he is trying to compromise, then the search space for a dictionary attack on a salted password is of size
2B*D,
where B is the number of bits of the random salt and D is the size of the list of words for the dictionary attack.
For example, if a system uses a 32-bit salt for each userid and its users pick passwords in a 500,000 word dictionary, then the search space for attacking salted passwords would be
232 * 500,000 = 2,147,483,648,000,000,
which is over 2 quadrillion.
Let’s say there are 500,000 words in the dictionary, and the length of salt is 32 bits.
Then all the possible combinations becomes 2^32 times 500,000, which makes over 2 quadrillion.
Try to calculate how long it takes to test this large number of combinations if the attacker can make 1000 trials per second.
It should be huge, longer than a million years.
8
Linux Password Files
/etc/passwd: basic user & password info (world-readable)
/etc/shadow: encrypted password info
Based on one-way function
Readable only by superuser
Linux (and UNIX) has two files to keep the password information.
The password file keeps the basic user information including user ID, and the shadow file stores the hashed password information with the salt information.
The shadow file is thus accessible only by the root user.
9
/etc/passwd (Ubuntu)
Format: username:password:UID:GID:UID_info:home_dir:shell
This screen shows an example of the password file in Linux.
You can see the user id in the first column.
10
/etc/shadow (Ubuntu)
Format: username:password:last_change:minimum:maximum:warn:inactive:expire
And this screen shows an example of the shadow file.
Right next to the user id, you can see the hashed output there.
11
Access Control Models
Discretionary Access Control (DAC)
The owner grants access to others
The owner may define the type of access (read/write/execute) given to others
Mandatory Access Control (MAC)
The administrator grants access to users
Multiple levels of security for users and documents
Levels (example in military): Top secret > Secret > Confidential > Restricted > Unclassified
DAC is the standard model used in operating systems
12
I will briefly introduce two types of access control models.
In the Discretionary Access Control (DAC), the owner has the right to give access to others for his/her files.
In another access control model, known as Mandatory Access Control (MAC), the administrator grants access to users, based on levels from Top secret to Unclassified, for example.
The DAC model is the standard model used in many operating systems.
Access Control Entries and Lists
An Access Control List (ACL) for a resource (e.g., a file or folder) is a sorted list of zero or more Access Control Entries (ACEs)
An ACE specifies that a certain set of accesses (e.g., read, execute and write) to the resources is allowed or denied for a user or group
Examples of ACEs for folder “CSCI351_Grades”
Bob; Read; Allow
TAs; Read; Allow
TWD; Read, Write; Allow
Bob; Write; Deny
TAs; Write; Allow
An access control entry is an element of an access control list.
And each entry specifies a certain set of accesses, as shown in the example.
13
Closed vs. Open Policy
Closed policy
Also called “default secure”
Give Tom read access to “foo”
Give Bob r/w access to “bar”
Tom: I would like to read “foo”
Access allowed
Tom: I would like to read “bar”
Access denied
Open Policy
Access is allowed by default
Deny Tom read access to “foo”
Deny Bob r/w access to “bar”
Tom: I would like to read “foo”
Access denied
Tom: I would like to read “bar”
Access allowed
14
There are two types of policies when setting up access control list.
The closed policy is known as “default secure”.
If not specified, access is denied.
The opposite is open policy, which allows all access by default.
Closed Policy with Negative Authorizations and Deny Priority
Give Tom r/w access to “bar”
Deny Tom write access to “bar”
Tom: I would like to read “bar”
Access allowed
Tom: I would like to write “bar”
Access denied
Policy is used by Windows to manage access control to the file system
In case of the closed policy with negation, the deny policy has a greater priority than the allow policy.
In this example, initially Tom was given r/w access to “bar”, but the next policy does not allow Tom to write to “bar”.
For the first access for reading, the access is allowed.
For the second example for writing, what happens?
The access should be denied.
15
Linux vs. Windows
Linux
Allow-only ACEs
Access to file depends on ACL of file and of all its ancestor folders
Start at root of file system
Traverse path of folders
Each folder must have execute (cd) permission
Different paths to same file not equivalent
File’s ACL must allow requested access
Windows
Allow and deny ACEs
By default, deny ACEs precede allow ones
Access to file depends only on file’s ACL
ACLs of ancestors ignored when access is requested
Permissions set on a folder usually propagated to descendants (inheritance)
System keeps track of inherited ACE’s
This slide compares Linux and Windows regarding the implementation of access control entries.
16
Linux File Access Control
File Access Control for:
Files
Directories
Therefore…
\dev\ : devices
\mnt\ : mounted file systems
What else? Sockets, pipes, symbolic links…
17
Now, I am going to briefly introduce the file access control implemented in Linux.
In Linux, file access control is mainly for files and directories in the hard drive, flash drive, and other mounted file systems.
Linux Permissions
Standard for all Linux/UNIXes
Every file is owned by a user and has an associated group
Permissions often displayed in compact 10-character notation
To see permissions, use ls –l
jk@sphere:~/test$ ls –l
total 0
-rw-r----- 1 jk ugrad 0 2005-10-13 07:18 file1
-rwxrwxrwx 1 jk ugrad 0 2005-10-13 07:18 file2
18
Previously, we studied on the file permission matrix for owner, group, and world, with a sequence of rwx.
Then what does it mean by the first digit?
The dash in the first digit indicates that the permission is for a file.
Permissions for Directories
Permissions bits interpreted differently for directories
Read bit allows listing names of files in directory, but not their properties like size and permissions
Write bit allows creating and deleting files within the directory
Execute bit allows entering the directory and getting properties of files in the directory
Lines for directories in ls –l output begin with d, as below:
jk@sphere:~/test$ ls –l
Total 4
drwxr-xr-x 2 jk ugrad 4096 2005-10-13 07:37 dir1
-rw-r--r-- 1 jk ugrad 0 2005-10-13 07:18 file1
19
As can be seen in this slide for “dir1”, the first digit is ‘d’ rather than dash.
This indicates that this permission is for a directory (or folder).
The next permission starts with a dash, and this is for a file and the name is “file1”.
Working Graphically with Permissions
Several Linux GUIs exist for displaying and changing permissions
In KDE’s file manager Konqueror, right-click on a file and choose Properties, and click on the Permissions tab:
Changes can be made here (more about changes later)
20
We can also set this permission using a graphical tool as shown in the slide.
Special Permission Bits
Three other permission bits exist
Set-user-ID (“suid” or “setuid”) bit
Set-group-ID (“sgid” or “setgid”) bit
Sticky bit
21
We next learn some special permission bits.
The set-user-ID bit and set-group-ID bit are for privilege escalation.
The sticky bit is to protect the file from being renamed or deleted by somebody else other than the owner.
Set-user-ID
Set-user-ID (“suid” or “setuid”) bit
On executable files, causes the program to run as file owner regardless of who runs it
Ignored for everything else
In 10-character display, replaces the 4th character (x or -) with s (or S if not also executable)
-rwsr-xr-x: setuid, executable by all
-rwxr-xr-x: executable by all, but not setuid
-rwSr--r--: setuid, but not executable - not useful
22
As mentioned, the set-user-ID bit is for privilege escalation, and if this bit is set on, the group and others can execute this file with the owner’s permission.
In the example, you can see the owner’s permission is set to rws rather than rwx, which indicates the set-user-ID bit is set on.
Set-group-ID
Set-group-ID (“sgid” or “setgid”) bit
On executable files, causes the program to run with the file’s group, regardless of whether the user who runs it is in that group
On directories, causes files created within the directory to have the same group as the directory, useful for directories shared by multiple users with different default groups
Ignored for everything else
In 10-character display, replaces 7th character (x or -) with s (or S if not also executable)
-rwxr-sr-x: setgid file, executable by all
drwxrwsr-x: setgid directory; files within will have group of directory
-rw-r-Sr--: setgid file, but not executable - not useful
23
The set-group-ID is almost the same as the set-user-ID.
The only difference is that others execute this file with the file’s group permission, while the set-user-ID is executed with the owner’s permission.
The set-group-ID bit is set on in the group permission bit.
In the example, we can see that the execute bit for group is set to ‘s’.
Sticky Bit
On directories, prevents users from deleting or renaming files they do not own
Ignored for everything else
In 10-character display, replaces 10th character (x or -) with t (or T if not also executable)
drwxrwxrwt: sticky bit set, full access for everyone
drwxrwx--T: sticky bit set, full access by user/group
drwxr--r-T: sticky, full owner access, others can read (useless)
24
The owners may want to prevent somebody else from deleting or renaming files on a directory that the owner owns.
Then we set on the sticky bit.
As in the example, if the last bit is set to “t”, then this indicates the sticky bit is set on.
With this sticky bit, the owner can still rename or delete the file, but the group and others are not allowed to do so.
Working Graphically with Special Bits
Special permission bits can also be displayed and changed through a GUI
In Konqueror’s Permissions window, click Advanced Permissions:
Changes can be made here (more about changes later)
25
Linux also provides a graphical user interface for the special permission setting.
Root
“root” account is a super-user account, like Administrator on Windows
Multiple roots possible
File permissions do not restrict root
This is dangerous, but necessary, and OK with good practices
26
The root account is like a super user or administrator account, and root can access any files and directories with the full privilege.
So, keeping the account secure is very important for system security.
Becoming Root
su
Changes home directory, PATH, and shell to that of root, but doesn’t touch most of environment and doesn’t run login scripts
su -
Logs in as root just as if root had done so normally
sudo <command>
Run just one command as root
su [-] <user>
Become another non-root user
Root does not require to enter password
27
There are several commands to switch to the root, including the su command, which is read “superuser”.
What is an Exploit?
An exploit is any input (i.e., a piece of software, an argument string, or sequence of commands) that takes advantage of a bug, glitch or vulnerability in order to cause an attack
An attack is an unintended or unanticipated behavior that occurs on computer software, hardware, or something electronic and that brings an advantage to the attacker
Let’s move on to the second topic of application program security.
By definition, an exploit is any input that takes advantage of a bug that causes an attack.
Operating Systems: Basic Concepts
2009-01-28
CS 166
28
Buffer Overflow Attack
One of the most common OS bugs is a buffer overflow
The developer fails to include code that checks whether an input string fits into its buffer array
An input to the running process exceeds the length of the buffer
The input string overwrites a portion of the memory of the process
Causes the application to behave improperly and unexpectedly
Effect of a buffer overflow
The process can operate on malicious data or execute malicious code passed in by the attacker
If the process is executed as root, the malicious code will be executing with root privileges
29
And one of the most common and critical OS bugs is a buffer overflow, exploited by a large set of viruses and worms.
If this type of attack is successful, the attacker can execute malicious code in the victim’s machine.
If the current process executing the malicious program is root, then the attacker gains the root privilege and can do whatever he/she wants in the victim’s machine.
2009-01-28
Operating Systems: Basic Concepts
CS 166
Buffer Overflow
Buffer overflow vulnerabilities
Out-of-bounds memory accesses used to corrupt program’s intended behavior
Most common class of implementation flaw
Example:
char sample[10];
sample[10] = ‘B’;
To understand buffer overflow, let’s take a look at this code.
If we assign a character to the sample array with index 10, what would happen?
As you know, the valid index for sample is from 0 to 9.
30
An Execution Result
Fortunately, many operating systems detect this type of mistake and forcefully terminates the program.
However, if the operating system does not have this functionality, the buffer overflow causes to change the content in the memory that may be occupied by another variable or the system.
31
Places where a buffer can overflow
(1) Affects user’s data
(2) Affects user’s code
(3) Affects system data
(4) Affects system code
This slide shows four consequences due to the buffer overflow, affecting user’s data or code, or it could be the memory space occupied by the operating system.
32
Buffer Overflow Example
char buf[80];
void vulnerable() {
gets(buf);
}
gets() reads all input bytes available on stdin, and stores them into buf[]
Any risk here?
What if input has more than 80 bytes?
gets() writes past end of buf, overwriting some other part of memory
Results?
Let’s take a look at another example of buffer overflow.
In this code, gets() takes the input from the command line, and puts the input to the buf, the length of which is 80.
If the length of input is less than or equal to 80, then we are happy.
But what if input has more than 80 bytes?
This will cause a buffer overflow.
33
Modified Example
char buf[80];
int authenticated = 0;
void vulnerable() {
gets(buf);
}
A login routine sets authenticated flag only if user proves knowledge of password
Any risk?
authenticated stored immediately after buf
Attacker “writes” data after end of buf
Attacker supplies 81 bytes (81st set non-zero)
Makes authenticated flag true
Attacker gains access: security breach!
In this example, right next to the buf array, an integer variable of authenticated resides in the memory space.
And a login routine sets authenticated flag only if user gives the correct password.
But using a buffer overflow attack, the attacker can set the flag ON, by supplying 81 bytes of input and the 81st element has a non-zero value.
Finally, the attacker gains access which causes security breach.
34
Malicious Code Injection Attack
char buf[80];
int (*fnptr)();
…
Function pointer fnptr invoked elsewhere
Any risk?
What can attacker do?
Can overwrite fnptr with any address, redirecting program execution
Crafty attacker:
Input contains malicious machine instructions, followed by pointer to overwrite fnptr
When fnptr is next invoked, flow of control redirected to malicious code
If a buffer overflow attack changes a function pointer, and later the function is invoked, the control is redirected to a malicious code.
This type of attack is known as Malicious Code Injection Attack.
35
Buffer Exploit History
How likely are the conditions required to exploit buffer overflows?
Actually fairly rare
But, first Internet worm (Morris worm) spread using several attacks
One used buffer overflow to overwrite authenticated flag in in.fingerd (network finger daemon)
Attackers have discovered much more effective methods of malicious code injection
Not surprisingly, there have been numerous attacks exploiting buffer overflow bugs.
And the first Internet worm (known as Morris worm) was also based on a buffer overflow attack.
36
Memory Layout for Program
Image from http://www.geeksforgeeks.org/memory-layout-of-c-program/
The last topic of this lecture is Stack Smashing Attack, which is a type of buffer overflow in the stack segment.
As can be seen in the memory layout for a program, stack grows from higher address to lower address.
37
The Stack
Prog Ctr = Return address
Stack Ptr = Stack frame
Pn = Parameters passed when calling
When a function is invoked, the program uses the stack segment to save the arguments that are passed to the called function, then the return address and the stack frame address are saved.
The return address (or Program Counter in the example) points to the return address that the program jumps once this function is terminated.
The stack frame is the stack address for the caller function that invoked the current function.
38
Stack after A calls B
Stack for A
Local variables for B
Return address when B is done
Stack address for A
So let’s assume function A invokes function B.
We can see the stack space for A, and B’s stack space starts next.
You can see that the program counter points to the instruction right next to “call B” in procedure A,
And the stack pointer points to the stack for A.
Once the procedure B is terminated, the B’s stack will be freed and the program gets back to the stack for procedure A.
39
Stack Smashing Attack
Stack for A
buf[80]
other local vars for B
High address
Low address
buf[79]
buf[0]
void vulnerable()
{
char buf[80];
gets(buf);
}
Let’s think about the buffer overflow attack using the code above.
As the buf zero is located in the lowest address and buf 79 is in the highest address, the memory snapshot would be like this.
What if there is a buffer overflow attack?
Then stack pointer and return address can be corrupted.
If the return address is compromised, that is what we call stack smashing attack.
40
Stack Smashing Attack
Stack for A
other local vars for B
High address
Low address
buf[79]
buf[0]
Shell code
Does not matter
X
&buf[0]
X
Input: 88 bytes with malicious shell code
void vulnerable()
{
char buf[80];
gets(buf);
}
This slide shows the consequence of stack smashing attack.
The malicious user gave input that is 88 bytes long including malicious shell code.
We can see that the corrupted return address now points to the malicious shell code.
Once the procedure B is terminated, the shell code will be invoked.
41
Stack Smashing Attack
First, attacker stashes malicious code sequence somewhere in program’s address space
Next, attacker provides carefully-chosen 88-byte sequence
Last four bytes chosen to hold code’s address overwrite saved return address
When vulnerable() returns, CPU loads attacker’s return addr – handling control over to attacker’s malicious code
This slide summarizes how stack smashing attack can be done.
42
Overflow Countermeasures
Staying within bounds
Check lengths before writing
Confirm that array subscripts are within limits
Double-check boundary condition code for off-by-one errors
Limit input to the number of acceptable characters
Limit programs’ privileges to reduce potential harm
Many languages have overflow protections
Code analyzers can identify many overflow vulnerabilities
Canary values in stack to signal modification
What would be countermeasures then?
The programmer should check array bounds.
In fact, many languages have overflow protection, including canary.
43
Stack-based buffer overflow detection using a random canary
The canary is placed in the stack prior to the return address, so that any attempt to over-write the return address also over-writes the canary.
Buffer
Other local variables
Canary (random)
Return address
Other data
Buffer
Corrupt return address
Attack code
Normal (safe) stack configuration:
Buffer overflow attack attempt:
Overflow data
x
In this canary technique, there is a space called canary just before the return address field.
If the return address is overwritten by a buffer overflow attack, then the canary field should also be overwritten.
By checking the canary value, it is possible to check whether the return address field is corrupted or not.
44
Other Programming Oversights
Undocumented access points (backdoors)
Off-by-one errors
Integer overflows
Un-terminated null-terminated string
Parameter length, type, or number errors
Unsafe utility libraries
There are other programming oversights, including backdoors, integer overflows, and so forth, which can be used by attackers to get access.
45
Stack
P3
P2
P1
Prog Ctr
Stack Ptr
Direction of growth
Stack
P3
P2
P1
Prog Ctr
Stack Ptr
Direction of
growth