CS Unplugged

“CS Unplugged is a collection of free learning activities that teach Computer Science through engaging games and puzzles that use cards, string, crayons and lots of running around.

The activities introduce students to Computational Thinking through concepts such as binary numbers, algorithms and data compression, separated from the distractions and technical details of having to use computers. Importantly, no programming is required to engage with these ideas!

CS Unplugged is suitable for people of all ages, from elementary school to seniors, and from many countries and backgrounds. Unplugged has been used around the world for over twenty years, in classrooms, science centers, homes, and even for holiday events in a park!”

Source: CS Unplugged Website

Download the book from here

Advertisements

IDA plugins and scripts

A collection of IDA plugins and scripts can be found in the following places:

  • OpenRCE: a collection of about 80 plugins.
  • devttys0: several IDA plugins and scripts from Craig Heffner.
  • PatchDiff2:  IDA plugin that can analyze two IDB files and find the differences between both.
  • RebuildFunctions: rebuild functions and fix the disassemble code in IDA (kudos to Santamarta).
  • bniemczyk: a collection of reversing tools for IDA.
  • tuts4you:  several plugins from tuts 4 you community.
  • flare-ida: IDA utilities from FLARE team.
  • newgre: three IDA plugins from newgre.net
  • IDApalace: plugins from old.idapalace.net
  • IDA ClassInformer: IDA plugin to fix/extract/view RTTI information.
  • IDAPython: IDA plugin that integrates Python, allowing scripts to run in IDA Pro.
  • Diaphora: a program diffing plugin for, at the moment, IDA Pro.
  • idapathfinder: an IDA plugin to graph all paths between two functions.
  • IDAScript: a wrapper around IDA that makes it easy to automate the execution of IDA scripts against target files from the command line.
  • Hex-Rays: sample plugins from IDA official website. Useful information can be found at the hexblog as well.
  • IDACyber: a plugin for the Interactive Disassembler which is capable of visualizing the currently loaded IDB’s data (useful for identifying structures and patterns of binary blobs where extended information such as a header is not available).
  • HeapViewer: An IDA Pro plugin to examine the heap, focused on exploit development.

Synthetic Testing of Circuit Breakers

In this post, we will analyze the circuit below for the synthetic testing of Circuit Breakers (CBs) in the case when CB is open and close. The idea is to solve the electrical transient mathematically but the following approach will be based on a simulation analysis of synthetic testing.

circuit
.

According to [1], synthetic tests are based on a two part test that is done all at once. “The test is performed by combining a moderate voltage source which supplies the full primary short circuit current with a second, high voltage, low current, power source which injects a high frequency, high voltage pulse at a precise time near the natural current zero of the primary high current. The purpose of synthetic tests is to reproduce conditions that closely simulate those that prevail in the interrupter during the high current arcing and the high voltage recovery periods” [5].

There are a number of synthetic test schemes that have been developed, but in practice they are all only a variation of the basic voltage or current injection schemes [1]:

1. Current Injection Method

This method is characterized by the injection of a pulse of current that is supplied by the high voltage source.

The two major current injection methods are:

  • Parallel Current Injection Circuit

Figure 1: Parallel Current Injection Test Circuit [1].
Figure 1: Parallel Current Injection Test Circuit [1].
Figure 2: Parallel Current Injection; Current Waveshape [1].
Figure 2: Parallel Current Injection; Current Waveshape [1].

  • Series Current Injection Circuit

Figure 3: Series Current Injection Test Circuit [1].
Figure 3: Series Current Injection Test Circuit [1].
Figure 4:  Series Current Injection Current Waveshapes [1].
Figure 4: Series Current Injection Current Waveshapes [1].
2. Voltage Injection Method

Figure 5: Voltage Injection Test Circuit [1].
Figure 5: Voltage Injection Test Circuit [1].

In practice, all testing laboratories more frequently use the parallel current injection technique test (Figure 1) [1] [5], described in detail below:

The high current source is composed of:

  • A short circuit generator,
  • A back-up CB for the protection of the test generator,
  • A set of current limiting reactors,
  • A making switch and,
  • An Isolation Breaker (IB) that isolates the current circuit from the high voltage circuit.

The high voltage section of the circuit is made up of:

  • A high voltage source consisting of a capacitor bank that is charged to a predetermined high voltage level. Connected in series with the capacitor is one side of a triggered spark gap (TG).
  • The other side of the trigger gap is connected to a group of frequency tuning reactors.
  • Connected in series with these reactors there is a short line fault (SLF) TRV shaping network, which consists of a combination of capacitors and reactors that in most instances are connected in a classical pi (π) circuit configuration.

The schematic diagram of the parallel current injection shown in Figure 1 is presented again in a more simplified manner in Figure 6 (in a red rectangle the circuit part of our initial problem). The test is initiated by closing the making switch (MS), which initiates the flow of the current i1, from the high current source through the IB and the Test Breaker (TB). As the current approaches its zero crossing the spark gap is triggered and at time t1 (see Figure 2) the injected current i2 begins to flow. The current i1 + i2 flows through the TB until the time t2 is reached. This is the time when the main current i1 goes to zero and when the IB separates the two power sources. At time t3 the injected current is interrupted and the high voltage supplied by the high voltage source provides the desired TRV which subsequently appears across the terminals of the CB that is being tested.

Figure 6: Schematic diagram of a parallel current injection synthetic test circuit.
Figure 6: Schematic diagram of a parallel current injection synthetic test circuit.

IEC Standard of Transient Recovery Voltage (TRV) Envelops

Short circuit test requires circuit with response specified by IEC Standards [7] in order to control the TRV. The TRV produced from tests must follow the specification as required by the standards.

Case of Two Parameters [6]

Case of Four Parameters [8]

Figure 7: Circuit to analyze.
Figure 7: Circuit to analyze.

Based on what we want to solve and what we explain above related to synthetic testing of CBs, below is the developed parallel current injection model in MATLAB/Simulink (the files can be emailed upon request):

Figure 8: Single phase parallel current injection circuit for synthetic test.
Figure 8: Single phase parallel current injection circuit for synthetic test.

Based on ANSI/IEEE Std. C37 [1] parallel current injection circuit operation can be described as follows:

  1. The test is initiated by closing the making switch which allows current i1 to flow through the current limiting reactor Lc, the auxiliary CB, and the TB.

  2. Prior to the interaction interval, the spark gap is triggered at time t1, (see Figure 1) and current i2 is injected and flows through the high-voltage reactor Lv, and TB.

  3. The current through the TB is i1 plus i2 until time t2 when the auxiliary breaker isolates the current circuit from the voltage circuit.

  4. The current through the TB is i2 until time t3, when the TB interrupts and the transient recovery voltage (TRV) is impressed across the TB.

Simulation Results

Figure 9 shows the voltage across the TB before and after the interruption. As shown the arc voltage was appearing across the TB during the separation of the contacts. Then, when it comes to current zero, the TB totally opens the contacts with very small amount of current flowing through the TB.

Figure 9: Voltage across the test breaker in respect with time.
Figure 9: Voltage across the TB in respect with time.

Figure 10 shows the short circuit current supplied by the generator forced to the TB. Short circuit current waveform was affected by the DC and AC components in the test circuit.

Figure 10: Short circuit current from the generator in respect with time.
Figure 10: Short circuit current from the generator in respect with time.

A synthetic test is also about to inject the current pulse at a few microseconds before the short circuit current reaches the zero point in order to provide restriking voltage across the TB. Therefore, the capacitor bank has to be fully charged before it is used to supply the injection current. Figure 11 shows the charging and discharging process of the capacitor bank.

Figure 11: Voltage at the capacitor bank during charging and discharging in respect with time.
Figure 11: Voltage at the capacitor bank during charging and discharging in respect with time.

Figure 12 shows the current triggered from the capacitor bank in order to provide the restriking voltage to TB after the auxiliary breaker isolate the short circuit current from the TB. The magnitude of the injected current should be adjusted so that the rate of change of the injected current (di/dt) and the rate of change of the corresponding rated power frequency current (di/dt)p are equal at their respective current zeros. The timing for initiation of the current pulse is controlled so that the time during which the arc is fed only by injected, current is no more than one-quarter of the period of the injected frequency [5].

Figure 12: Current releases from the triggered spark gap in respect with time.
Figure 12: Current releases from the triggered spark gap in respect with time.

Total current that flows through the TB during the synthetic test is shown in Figure 13. The most important part of this simulation result is the effect of injection current as shown in Figure 14. It is recommended [1] that the frequency for the injected current to be kept within the range of 300 to 1000 Hz. The limits depend primarily on the characteristics of the arc voltage.

Figure 13: Current flowing through the test breaker with the synthetic circuit
Figure 13: Current flowing through the TB with the synthetic circuit
Figure 14: Short circuit current; injected current and total current on test breaker
Figure 14: Short circuit current; injected current and total current on TB

The final analysis for the synthetic simulation is to show the unsuccessful interruption result of the TB. The failure to recover the voltage means the TB has failed to perform as fault clearer. Figure 15 shows that the TB fails to isolate the fault because it allows the restriking of short circuit current, where the short circuit current continues to flow through the TB after the interruption.

Figure 15: Short circuit current continuing to flow after the interruption
Figure 15: Short circuit current continuing to flow after the interruption

Discussion

Results obtained from the synthetic test simulation were conducted using the current injection method. In principle, the current injection method and the voltage injection method are the same. As mentioned before, the only difference is that the output of high voltage source is injected across the open contacts of the TB following the interruption of the short circuit current. It is recommended that both test methods are modeled to perform the simulation. However voltage injection method is not too popular as a testing method because it requires a very accurate timing for the voltage injection.

Basically in actual synthetic test, the main disadvantage is that these tests are primarily a single loop test where it is still very difficult to do a fast reclosing with extended arcing times. Another disadvantage is that this method is not suitable for testing interrupters which have impedance connected in parallel with the interrupter contacts in which case it is likely that the full recovery voltage cannot be attained due to the power limitations of the high voltage source [5].

For failure interruption simulation, the test circuit breaker is modeled to be reclosed after the interruption to show that the breaker fails to clear the fault. The arc fails to extinguish during the contacts separation whereas the breaker allows the short circuit current to continue flowing.

Appendix: Explanations about the elements of the developed model

As mentioned, synthetic test has two main sections, the current source and the voltage source. The current source is a short circuit current supply with possible maximum current. It has high current flow at low voltage. For the voltage source it is high voltage supply and has low current flow. In real synthetic test, voltage source is a fully charged capacitor bank before it can be applied for testing. For the purposes of a simulation, this capacitor can be modeled as a dc voltage source. The spark gap can be modeled as a controlled time switch, because in real synthetic test, the spark was triggered with special controlled circuit. The additional circuit is to control spark triggered at the desired moment and slightly before the short circuit current reaches it natural zero.

  1. Short circuit generator1

Purpose: to provide the energy used during the test (high current through the TB in a short duration). For the simulation, the generator was modeled as AC supply with RL impedance.

Notes: The transient and sub-transient reactances must be as small as possible to provide the maximum short circuit current (leakage flux must be minimal and individual windings as close coupled as possible) [9].

  1. Master Circuit Breaker

2Purpose: to protect the equipment within the testing station against the consequences of a failure of the TB to interrupt the fault current.

  1. Auxiliary Circuit Breaker

3Purpose: to isolate the current source from the high voltage source and must, therefore, have a performance superior to that of the CB being tested.

  1. Making Switch

4

Purpose: to apply short circuit current at the desired moment during the test. This switch is used to connect the generator to the test circuit at a precise point on the voltage wave and high speed operation is essential to enable the precision in closing instant to be obtained. Pre-arcing during the closure of the switch must be minimal because it may affect the consistency of point on wave control [5].

  1. Current Limiting Reactors

5

Purpose: located between the generator and transformer (step up the voltage from voltage source to the secondary side. Not necessary its usage if the voltage source already had desired performance) together with resistors, so that before the current enter the test circuit, to control the current within limits together with the circuit power factor [9]

  1. Test Breaker (TB)

6

Purpose: the tested circuit breaker. It might be a single phase or multi-phase depend on synthetic test circuit used.

  1. TRV shaping circuit

7

Purpose: to control the transient recovery voltage (TRV) and rate of raise restriking voltage (RRRV).

  1. Charged Capacitor Bank (High Voltage Source)

8

Purpose: to supply high voltage to the test circuit breaker. Banks of capacitors of up to hundreds of MVAR are required for the testing of CBs for the switching of shunt capacitor installations and are also used to test for overhead line and cable no-load switching. Capacitors are also required for the control of the circuit natural frequency for normal short circuit tests [9]. The capacitor bank is modeled so that it could supply 800 kV.

  1. Triggered Spark Gap

9

Purpose: to apply high voltage to the TB at desired moment. It controls the instant of injection in both current and voltage schemes.

  1. Artificial Short Line (SL)

10

Purpose: to simulate the distance between the fault located on an overhead line from a switching station i.e. to simulate the varied conditions presented by single and bundle conductors. The majority of testing stations use an artificial line comprising various series-parallel combinations of inductance and capacitance.

References

[1] IEEE Guide for Synthetic Fault Testing of AC High-Voltage Circuit Breakers Rated on a Symmetrical Current Basis,” ANSI/IEEE Std C37.081-1981 , vol., no., pp.0_1,, 1981

[2] Wilkinson, K. J R; Mortlock, J.R., “Synthetic testing of circuit-breakers,” Electrical Engineers – Part II: Power Engineering, Journal of the Institution of , vol.89, no.8, pp.137,142, April 1942.

[3] Jamnani, J.G.; Kanitkar, S.A., “Design, simulation and comparison of synthetic test circuits for extra high voltage circuit breakers,” Information and Communication Technology in Electrical Sciences (ICTES 2007), 2007. ICTES. IET-UK International Conference on , vol., no., pp.464,468, 20-22 Dec. 2007.

[4] Legros, W.P.; Genon, A.M.; Morant, M.M.; Scarpa, P.G.; Planche, R.; Guilloux, C., “Computer aided design of synthetic test circuits for high voltage circuit-breakers,” Power Delivery, IEEE Transactions on , vol.4, no.2, pp.1049,1055, April 1989

[5] High Voltage Circuit Breakers, Design and Applications, Ruben Garzon, MARCEL DEKKER INC, New York – Basel, 2002.

[6] Jamnani, J. G.; Kanitkar, S.A., “Design and Simulation of 2-Parameters TRV Synthetic Testing Circuit for Medium Voltage Circuit Breakers,” Electrical and Computer Engineering, 2006. ICECE ’06. International Conference on , vol., no., pp.1,4, 19-21 Dec. 2006

[7] Penkov, D.; Vollet, C.; Durand, C.; Husin, A. M.; Edey, K. C., “IEC standard high voltage circuit-breakers: Practical guidelines for overvoltage protection in generator applications,” Petroleum and Chemical Industry Conference Europe Conference Proceedings (PCIC EUROPE), 2012 , vol., no., pp.1,12, 19-21 June 2012

[8] Jamnani, J. G.; Kanitkar, S.A., “Design and Simulation of 4-Parameters TRV Synthetic Testing Circuit for High Voltage Circuit Breakers,” Electrical and Computer Engineering, 2006. ICECE ’06. International Conference on , vol., no., pp.25,28, 19-21 Dec. 2006

[9] C. H Flurscheim, Dr. A. T. Johns, G. Ratcliff and Prof. A. Wright, “Power circuit breaker theory and design”, Revised Edition, Peter Peregrinus Ltd (behalf of the IEE), 1982, ISBN: 0-906048-72-2

VFS, proc and root filesystems

The VFS (Virtual File System) is a subsystem of the kernel that implements the file and filesystem-related interfaces provided to user-space programs. All filesystems rely on the VFS in order to coexist and interoperate. Figure 1 shows the three major layers of a filesystem implementation. The first layer is the filesystem interface based on the open(), read(), write() and close() calls and on file descriptors. The VFS, second layer, enables system calls to work regardless of the filesystem or underlying physical medium as Figure 2 indicates. The third layer of the architecture implements the file system type or the remote file system protocol.

Figure 1: Schematic view of a VFS [1].
Figure 1: Schematic view of a VFS [1].
Figure 2: The flow of data from user-space issuing a write() call, through the VFS’s generic system call, into the filesystem’s specific write method, and finally arriving at the physical media. [2].
Figure 2: The flow of data from user-space issuing a write() call, through the
VFS’s generic system call, into the filesystem’s specific write method, and finally arriving at the physical media. [2].
In other words, VFS provides a common file model that can represent any filesystem’s general feature and behavior. VFS layer serves two important tasks. First, it separates generic filesystem operations from their implementation by defining a clean VFS interface. For the same machine several implementations for the VFS interface may coexist and consequently allowing access to different types of file systems. Furthermore, with VFS a file can be uniquely represented throughout a network. VFS is based on a V-node, which is a file representation structure. V-node contains a numerical designator for a network-wide unique file. The kernel retains one V-node structure for each active node (directory or file). Linux however does not have V-node. Instead, a generic i-node structure is used. Although the implementations differ, the V-node is conceptually the same as a generic i-node. Both point to an i-node structure specific to the file system.

The flow of Figures 1 and 2 shows that VFS activates filesystem operations to handle requests (local or remote) according to their filesystem types. File handles are constructed form the relevant V-nodes and are passed as arguments to these procedures.

Figure 3 shows a generic overview of VFS that separates the filesystem-specific structures from the rest of the kernel by “translating” system calls to proper filesystem type functions.

Figure 3: Overview of filesystem management structure [3].
Figure 3: Overview of filesystem management structure [3].
The VFS is object-oriented. The four primary object types of the VFS are:

  • The superblock object, which represents a specific mounted filesystem.
  • The i-node object, which represents a specific file.
  • The dentry object, which represents a directory entry, which is a single component of a path.
  • The file object, which represents an open file as associated with a process.

Each of the above objects contain a pointer to a function table that lists the addresses of the actual functions that implement the defined operations (listed below) for that particular object. Hence, the VFS layer can perform an operation on one of the four above objects by calling the suitable function from the object’s function table without having knowledge of the kind of the object.

In each object an operation object is included that describes the methods that the kernel invokes against the four objects above:

  • The superblock operations object (<linux/fs.h>) contains methods such as write_inode() and sync_fs() that the kernel can invoke on a specific filesystem.
  • The i-node operations object (<linux/fs.h>) contains methods such as create() and link() that the kernel can invoke on a specific file.
  • The dentry operations object (<linux/dcache.h>) contains methods such as d_compare() and d_delete() that the kernel can invoke on a specific directory entry.
  • The file operations object (<linux/fs.h>) contains methods such as read() and write() that the kernel can invoke on an open file.

/proc filesystem (/procfs)

The /procfs (process filesystem) is an additional mechanism (registered to the VFS layer) for the kernel and kernel modules to send information to processes. It exists only in kernel memory and is typically mounted at /proc. Reading or writing files in /procfs invokes kernel functions that simulate reading or writing from a real file. /procfs contents are computed on demand according to user file I/O requests. In other words, /procfs provides a method of communication between kernel space and user space.

The /proc file implements two important functions: a directory structure and the file contents within. A UNIX filesystem is a set of file and directory i-nodes identified by their
i-node numbers. The /proc filesystem defines a unique and persistent i-node number for each directory and the associated files. Given this i-node number, /procfs identifies the required operation when a user tries to read from a file i-node or performs a lookup in a particular directory i-node. After the reading from one of these files, /procfs collects the appropriate information and formats it into textual form. Then, /procfs places this information into the requesting process’s read buffer.

The mapping from i-node number to information type splits the i-node number into two fields. In Linux the i-node number is 32 bits. The top 16 bits define the Process ID (PID) and the remaining bits define the type of information that is requested about that process. A zero PID in the i-node number means that the i-node contains global information. Separate global files exist in /proc to report information such as the kernel version, drivers currently running and performance statistics. The kernel of course can dynamically allocate new /proc i-node mappings. Each global /proc filesystem entry contains the file’s i-node number, file name and access permissions along with the special functions used to generate the file’s contents. Figures 4, 5 and 6 shows a tour into /proc filesystem.

Figure 4: Interactive tour of /proc.
Figure 4: Interactive tour of /proc.

/root filesystem

A filesystem* is a hierarchically structured tree. The root of the tree on UNIX-like operating systems is the root directory/filesystem which is identified by the slash character “/”. The sub-trees of the root directory include other subdirectories and files as shown in Figure 7.

A root filesystem is also contained (“root on root”) on the same partition on which the root directory is located (/root directory is where all the home directories for root user on a system are stored).

The root filesystem is the “parent” of the entire filesystem [6]. All other directories are “children” of this directory. The partition which the root filesystem resides on, is mounted during boot, i.e. when the system is booted up all the other filesystems are mounted to the root filesystem. If the root filesystem is corrupted that means that the system becomes unbootable (of course using a boot flash drive as special measure could be bootable).

*filesystem definition can be found in several papers, books and websites such as [7] and [8]: “A filesystem is the methods and data structures that an operating system uses to keep track of files on a disk or partition; that is, the way the files are organized on the disk.”

Figure 5: /proc CPU Information file.
Figure 5: /proc CPU Information file.
Figure 6: Information about Mozilla running process with PID 1797 in /proc.
Figure 6: Information about Mozilla running process with PID 1797 in /proc.

Figure 7: Linux file system layout from a RedHat system [5].
Figure 7: Linux file system layout from a RedHat system [5].
Important directories in Linux include:

/bin: Hold the most commonly used essential user programs.
/sbin: Hold essential maintenance or system programs (difference between the programs stored in /bin and /sbin is that the programs in /sbin are executable only by root).
/etc: Store the system wide configuration files required by many programs.
/home: The place where all the home directories for all the users on a system are stored.
/root: The directory where all the home directories for root user on a system are stored.
/dev: The special files representing hardware are kept in it.
/tmp and /var: Directories which are used to hold temporary files or files with constantly varying content.
/usr: Most programs and files directly relating to users of the system are stored.

/proc: Explained before. To sum up, it is a VFS, i.e. a special filesystem provided by the kernel as a way of providing information about the system to user programs. The main tasks of /proc filesystem is to provide information about the kernel and processes.

References

[1] Abraham Silberschatz, Peter B. Galvin, Greg Gagne, “Operating System Concepts”, 7th edition,
[2] Linux Kernel Development, 3rd edition.
[3] Linux Virtual FileSystem, Online: http://bethechip.com/
[4] Advanced Linux Programming, Online: http://www.advancedlinuxprogramming.com/
[5] General overview of the Linux file system, Online: http://www.tldp.org/LDP/intro-linux/html/sect_03_01.html
[6] Sven Vermeulen, “Linux Sea”, Chapter 5: The Linux File System
[7] Wikipedia, File System, Online: http://en.wikipedia.org/wiki/File_system
[8] Moshe Bar, “Linux File Systems”.

Can Machines Think?

alan_turing
Alan Turing

Alan Turing in his famous “Computing Machinery and Intelligence” (published in 1950) initially addresses the question “can machine think?” but later he forms the problem in terms of a game, which is called the “Imitation Game”. The reason for that approach is to avoid the ambiguity between the concepts “machine” and “think”.

The “Imitation Game” defines that three players are allowed to play: a man (A), a woman (B) and an interrogator (C) who may be of either sex. The object of the game is the determination of the sex between A and B by C. The interrogator is based in a closed room and he/she is allowed to put questions to A and B and give the conclusive answer in the form of determination of their gender identity. The point is for C to think and then deduce the answer from the way his questions about the physique of the persons in question are answered. A and B voices since they reveal their gender identity must be “transferred” into a typewritten form. Therefore, if the game requires a considerable thinking process and also if the A and B are replaced with a machine, the question that must be asked is if C is able to distinguish between the machine and the persons. Hence, Turing initial question “can machines think” after the replacement of the “Imitation Game” concludes to the determination criterion which states that a machine can think arises from the interrogator’s inability to distinguish the difference between the machine and the person.

The argument “machines can never make mistakes”.

Turing avoids to answer the simple question whether or not machine can make mistakes. He adopts “a more sympathetic attitude” and he introduces the distinction between errors of functioning and errors of conclusion. He mentions that the question whether or not machines can make mistakes depends on a confusion between those two kinds of mistakes. Firstly, he states that errors of functioning are based on an electrical or mechanical fault, which causes the machine to operate not the way that it was designed to. Considering a philosophical perspective and assuming that those errors could not be arise because of the mathematical fiction of those “abstract machines” then “machines can never make mistakes”. However, he emphasizes that in case they are physical objects (as practical machines are) and therefore not theoretical discussions then those errors are inevitable in case of mechanical or electrical faults. Secondly, Turing talks about errors of conclusion that “can only arise when some meaning is attached to the output signals of the machine”. An example of this kind of errors is having an output “30” in response to the input “15+16”. Humans make many errors of this second class and Turing points out that machines could also make errors of conclusion. If a machine is programmed to do for example mathematical operations in the way that people actually solve mathematical operations then the machine might as humans, answer to some mathematical operations with an incorrect result.

Cracking Passwords with JTR

The previous two posts covered a part of the theory behind password cracking. Now, we will show how to crack passwords of two famous leaked password hashes list: Formspring and Linkedin. If you need the lists drop me an email.

First, we started by using the single mode attack on John the Ripper (JTR). Of course we didn’t get any positive results since as we explained in the previous post single mode uses login names, GECOS and users’ home directory names as candidate passwords. In the virtual machine that we installed for the purposes of this tutorial there isn’t much information that can be used for this method:

harrys@harrys-VirtualBox:~$ john –single 
'/harrys/formspring.txt' 
Loaded 1 password hash (generic crypt(3) [?/64]) 
guesses: 0 time: 0:00:00:25 100% c/s: 105 trying: harrys1928 – hharrys1900 


harrys@harrys-VirtualBox:~$ john --single 
'/harrys/SHA1.txt' 
Loaded 1 password hash (generic crypt(3) [?/64]) 
guesses: 0 time: 0:00:00:25 100% c/s: 106 trying: harrys1928 – hharrys1900

Next, we used the dictionary mode attack. Unfortunately, we didn’t manage to crack any
passwords using this method although we used a variety of password dictionary lists. Let’s see some of the results for various dictionary lists that either are included in JTR or one can find online.

a. password.lst 

harrys@harrys-VirtualBox:~$ sudo john -- 
wordlist=/harrys/john/run/password.lst 
'/harrys/formspring.txt' 
Loaded 1 password hash (generic crypt(3) [?/64]) 
guesses: 0 time: 0:00:00:24 100% c/s: 143 trying: !@#$% - sss 

harrys@harrys-VirtualBox:~$ sudo john -- 
wordlist=/harrys/john/run/password.lst '/harrys/SHA1.txt' 
Loaded 1 password hash (generic crypt(3) [?/64]) 
guesses: 0 time: 0:00:00:35 100% c/s: 98.88 trying: !@#$% - sss 

b. common-passwords.txt 

harrys@harrys-VirtualBox:~$ sudo john -- 
wordlist='/harrys/Downloads/common-passwords.txt' 
'/harrys/formspring.txt' 
Loaded 1 password hash (generic crypt(3) [?/64]) 
guesses: 0 time: 0:00:00:06 100% c/s: 135 trying: uucp – zmodem 

harrys@harrys-VirtualBox:~$ sudo john -- 
wordlist='/harrys/Downloads/common-passwords.txt' 
'/harrys/SHA1.txt' 
Loaded 1 password hash (generic crypt(3) [?/64]) 
guesses: 0 time: 0:00:00:07 100% c/s: 116 trying: uucp - zmodem

c. Given-Names.txt 

harrys@harrys-VirtualBox:~$ sudo john -- 
wordlist='/harrys/Downloads/Given- 
Names.txt' '/harrys/formspring.txt' 
Loaded 1 password hash (generic crypt(3) [?/64]) 
guesses: 0 time: 0:00:01:27 100% c/s: 98.81 trying: Zainab – Zygmunt 

harrys@harrys-VirtualBox:~$ sudo john -- 
wordlist='/harrys/Downloads/Given- 
Names.txt' '/harrys/SHA1.txt' 
Loaded 1 password hash (generic crypt(3) [?/64]) 
guesses: 0 time: 0:00:01:03 100% c/s: 136 trying: Zainab – Zygmunt 

d. Huge-List.txt 

harrys@harrys-VirtualBox:~$ sudo john -- 
wordlist='/harrys/Downloads/Huge- 
List.txt' '/harrys/formspring.txt' 
7Loaded 1 password hash (generic crypt(3) [?/64]) 
guesses: 0 time: 0:01:43:14 100% c/s: 140 trying: gethostbyname/gethostbyaddr - Karntnerstrasse- Rotenturmstrasse 

harrys@harrys-VirtualBox:~$ sudo john -- 
wordlist='/harrys/Downloads/Huge- 
List.txt' '/harrys/SHA1.txt' 
Loaded 1 password hash (generic crypt(3) [?/64]) 
guesses: 0 time: 0:01:18:58 100% c/s: 183 trying: gethostbyname/gethostbyaddr - Karntnerstrasse- Rotenturmstrasse

We have to mention that JTR also supports hybrid attacks, i.e. attacks that check for variations of a word or a combination of dictionary words. This method like the dictionary attack didn’t help us to crack the provided password lists.

Let’s move to our approach using the brute force attack method. As we explained, it consists of systematically checking all possible keys or passwords until the correct one is found. The program goes through all the possible plaintexts, hashing each one of them and then comparing it to the input hash. JTR uses character frequency tables to try first plaintexts containing more frequently used characters. This method is useful for cracking passwords which do not appear in dictionary wordlists, but it does take a long time to run. The default incremental mode checks potential passwords up to 8 characters. Just to show how time consuming this method is, we let our computer running in this mode for 2 days but the only result we got is that the our pc got overheated.

JTR program has an option for brute force attack that can make this process quicker. If we have prior knowledge of the password format, we can make this operation faster, by using a variation in incremental mode that only checks certain formats. Specifically, if we run:

./john – format=[MODE] password_list_to_crack.txt

JTR will use the MODE that we specified.

For example, for SHA1 mode (Fig. 1) JTR achieves cracking SHA1 hashes by first guessing the password using dictionary and incremental mode, and then generates theSHA1 hash for this password. Then, it checks if the hash that was generated for the password matches a hash in our file. When JTR finds a match then we recover the password from the provided list.

Fig. 1: One iteration within SHA1 compression function [1].
Fig. 1: One iteration within SHA1 compression function [1].
Our goal at this point is to do some research and find which hash function our lists used.

Formspring list:

This list used SHA256 hash function to encrypt the data that contains. This conclusion is based on two facts. First the provided hashes in this list have the follow form:

51e9b7073797d875a8862fbba743f7febec03164db4fdf91f10987b95be1852b

That means that the output of this hash function has 64*4 = 256 bits. This narrow our options of hash functions to algorithms like HAVAL256, RIPEMD256, SHA-3-256, SHA256 and GOST. JTR supports the two last methods. We checked both of those two formats in JTR. The GOST format processing time was too long without any result. On the other hand the SHA256 algorithm format was faster and we came to the conclusion that formspring list is hashed by that function (Fig. 2). This fact is also supported by various sites.

Fig. 2. Applying SHA256 algorithm format to JTR.
Fig. 2. Applying SHA256 algorithm format to JTR.

Linkedin list:

This list used sha1 hash function to encrypt the data that contains. This conclusion is based on two facts. First the provided hashes in this list have the follow form:

37b5b1edf4f84a85d79d04d75fd8f8a1c3d2fbde

That means that the output of this hash function has 40*4 = 160 bits. This narrow our options of hash functions to algorithms like HAVAL160, RIPEMD160, SHA0, TIGER(2)-160 and SHA1. JTR supports only the last hash function and this is the function that it was used to hash the passwords. This argument is also supported by the fact that the list name is SHA1.txt and the confirmation by the LinkedIn blog after the list was leaked. The new unstable version of JTR supports a mode called raw-sha1-linkedin that is especially for this specific list that it was leaked from LinkedIn.

Before the presentation of our results, we should mention that we could use also rainbow tables with JTR although the program does not support this method per se. The idea is to create a dictionary file using JTR and another software (e.g. CowPatty) to generate rainbow tables. In this post we focus our interest onto brute force attach method which generates a hash for each password and then compare it immediately with the correct password hash.

Fig. 3. JTR results for formspring list (SHA256 format).
Fig. 3. JTR results for Formspring list (SHA256 format).
Fig. 4. JTR results for linkedin list (sha256 format).
Fig. 4. JTR results for Linkedin list (sha256 format).

All the results above were obtained through running JTR on our computer for thirteen hours (let it run more time will give more cracked passwords). The results are quite impressive. To understand what these results mean we used graphs for better representation.

Fig. 5. (a)
Fig. 5. (a) Graphical representation of the Formspring cracked list results: Cracked passwords as a function of time.
Fig. 5 (b). Graphical representation of the formspring cracked list results: Combinations per second as a function of time.
Fig. 5. (b) Graphical representation of the Formspring cracked list results: Combinations per second as a function of time.
Fig. 6. (a) Graphical representation of the linkedin cracked list results: Cracked passwords as a function of time.
Fig. 6. (a) Graphical representation of the Linkedin cracked list results: Cracked passwords as a function of time.
Fig. 6. (b) Graphical representation of the linkedin cracked list results: Combinations per second as a function of time.
Fig. 6. (b) Graphical representation of the Linkedin cracked list results: Combinations per second as a function of time.

For the Formspring list we are able to crack 1392 passwords in around nine and a half hours, whereas for the Linkedin list we cracked 1108644 passwords in around thirteen hours. For both lists the combinations per second are decreasing as the time runs and the guesses are increasing. Of course, if we were able to run the program for more time, then our results would be more impressive because we could present all the passwords from the hashed lists.

Observations

Based on the results presented in the previous paragraphs, a number of observations can be made: First, we noticed that the LinkedIn list is cracked easier than the Formspring list. That means that using the LinkedIn list we cracked faster more passwords than the Formspring list. The reason is that in the LinkedIn list passwords are stored as unsalted SHA1 hashes and thus it takes less amount of time to crack this list. Unsalted hashes are much less secure than salted hashes because the password is not merged with another combination and then hashed. So, it takes less time to recover the passwords from Linkedin list compared to the Formspring one. On the other hand, the Formspring list uses the SHA256 function to hash the password after the password is combined with a prep-ending salt. Hence, it takes more time for JTR to recover the passwords from the Formspring list. Another interesting observation is that JTR brute force attack cannot easily crack both lists after a considerable amount of time. Although JTR starts cracking password easily at the beginning, as the time is running JTR recovers less passwords than before because it checks for password with a larger length.

What is unique on those two password lists?

The cracked passwords from the Formspring list show that the formula that it was used to hash these data was SHA256(“00-99”+”password”), i.e. each password was hashed after a number with range from 00 to 99 (salt) prep-ends the password. For example the password named “harrys” was hashed using the SHA256 hash algorithm after mixed with a random number from 00 to 99, i.e. SHA256(“58”+”harrys”). This hash weak method is quite easy to be cracked since the used salt has a range of 100 possibilities.

A view at the LinkedIn list reveals that many of the hashes contain five zeros at the beginning. That is something impossible for passwords that are hashed with the SHA1 hash function. We assumed that someone replaced the first five digits of some hashes with zeros so we would not be able to crack them. We removed these lines starting with “00000” as they are obfuscated hashes. This technique can be done using the “grep” command, i.e. “grep -v ‘^00000′” which will exclude all the lines from Linkedin file containing the “00000” string. We can get the same result using the raw-sha1-linkedin format mode in JTR that works with the same way.