Categories
Random

Migrating to EJBCA from OpenSSL and TinyCA

Install and configure EJBCA

EJBCA 6.0.3 – http://www.ejbca.org/download.html

JBoss AS 7.1.1 Final – http://download.jboss.org/jbossas/7.1/jboss-as-7.1.1.Final/jboss-as-7.1.1.Final.zip

Prereqs:

Ref:

Detailed deployment guide: http://majic.rs/book/free-software-x509-cookbook/setting-up-ejbca-as-certification-authority

EJBCA doc: http://wiki.ejbca.org/

Architecture

Recommended architecture (source: http://ejbca.org/architecture.html)

Import existing OpenSSL CA

Step 1 – Export the OpenSSL priv key and cert to a PKCS#12 keystore:

openssl pkcs12 -export -out exitingCA1.p12 -inkey  \
        -in  -name existingCA1

Step 2 – Import the PKCS#12 keystore to EJBCA CA

/bin/ejbca.sh ca importca  existingCA1.p12

Step 3 – Verify import

/bin/ejbca.sh ra adduser

### IMPORTANT ###

Distinguished name order of openssl may be opposite of ejbca default configuration – http://www.csita.unige.it/software/free/ejbca/ … If so, this ordering must changed in ejbca configuration prior to deploying (can’t be set on a per CA basis)

Have not been able to replicate this issue in testing.

Import existing TinyCA CA

Basic Admin and User operations

Create and end entity profile for server/client entities

Step 1 – Create a Certificate Profile (http://wiki.ejbca.org/certificateprofiles)

Step 2 – Create and End Entity Profile (http://wiki.ejbca.org/endentityprofiles)

* EndEntities can be deleted using:

/bin/ejbca.sh ra delendentity 

Issuing certificates from CSRs

End entities need to be created for clients/servers that require certificates signed by our CA.

Step 1 – Create and End Entity (http://ejbca.org/userguide.html#Issue a new server certificate from a CSR)

Step 2 – Sign CSR using the End Entity which is associated with a CA

Importing existing certificates

EJBCA can create endentities and import their existing certificate one-by-one or in bulk (http://www.ejbca.org/docs/adminguide.html#Importing Certificates). Bulk inserts import all certificates under a single user which may not be desirable. Below is a script to import all certs in a directory one by one under a new endentity which will take the name of the certificate CN.

#!/bin/sh

# for each certificate in the directory
#       create and enduserentity
#       enduserentity username = certificate CN
#       enduserentity token/pwrd = certificate CN

EJBCA_HOME="/usr/share/ejbca"
IMPORT_DIR=$1
CA=$2
ENDENTITYPROFILE=$3
SSLCERTPROFILE=$4
AP="_OTE"

if [ $# -lt 4 ]; then
        echo "usage: import_existing_certs.sh    "
        exit 1
fi
for X in $IMPORT_DIR*.pem
do
        echo "######################################################"
        echo "Importing: " $X
        CN=$(openssl x509 -in $X -noout -text | grep Subject: | sed -n 's/^.*CN=\(.*\),*/\1/p')
        echo "CN: " $CN
        printf "Running import: %s ca importcert '%s' '%s' '%s' ACTIVE NULL '%s' '%s' '%s'\n" "$EJBCA_HOME/bin/ejbca.sh" "$CN" "$CN" "$CA" "$X" "$ENDENTITYPROFILE" "$SSLCERTPROFILE"
        $EJBCA_HOME/bin/ejbca.sh ca importcert "$CN$AP" "$CN$AP" "$CA" ACTIVE null $X $ENDENTITYPROFILE $SSLCERTPROFILE
        echo "######################################################"
done

Creating administrators

Create administrators that can sign CSR and revoke certificates: http://ejbca.org/userguide.html#Administrator%20roles

Revoking certificates

#Generate CRL via command line
# List CAs
/usr/share/ejbca/bin/ejbca.sh CA listcas
# Create new CRLs:
/usr/share/ejbca/bin/ejbca.sh CA createcrl "" -pem 
# Export CRL to file
/usr/share/ejbca/bin/ejbca.sh CA getcrl "" -pem .pem

Checking certificate validity/revoke status via OSCP

openssl ocsp -issuer gtld_CA_cert.pem -CAfile gtld_CA_cert.pem \
-cert gtld_registrar5.pem -req_text -url http://localhost:8080/ejbca/publicweb/status/ocsp

Monitoring expiring certs

/bin/ejbca.sh listexpired 100

 

Categories
Random

Getting started with ModSecurity

XSS, CSRF and similar types of web application attacks have overtaken SQL injections as the most commonly seen attacks on the internet (https://info.cenzic.com/2013-Application-Security-Trends-Report.html). A very large number of web application were written and deployed prior to the trend up in likelihood and awareness of XSS attacks. Thus, it is extremely important to have an effective method of testing for XSS vulnerabilities and mitigating them.

Changes to production code bases can be slow, costly and can miss unreported vulnerabilities quite easily. The use of application firewalls such as ModSecurity (https://github.com/SpiderLabs/ModSecurity/) become an increasingly attractive solution when faced with a decision on how to mitigate current and future XSS vulnerabilities.

Mod Security can be embedded with Apache, NGINX and IIS which is relativity straight forward. In cases where alternative web severs are being used ModSecurity can still be a viable option by creating a reverse proxy (using Apache of NGINX).

How can ModSecurity be used?

  • Alerting
  • Transforming
  • Blocking
  • and more

These functions can be enacted by rules.

A default action can be created for a group of rules using the configuration directive “SecDefaultAction

Using the following SecDefaultAction at the top of rule set that we want enable blocking and transforming on is a blunt method of protection. Redirection can also be used as a method of blocking.

A powerful web application firewall - free software!
A powerful web application firewall – free software!

Example of a default action to be applied by ruleset (note defaults cascade through the ruleset files):

SecDefaultAction “phase:2,log,auditlog,deny,status:403,tag:’Unspecified usage'”

Rulesets have been created by OWASP.

Using optional rulesets,  modsecurity_crs_16_session_hijacking.conf and modsecurity_crs_43_csrf_protection.conf ModSecurity can provide protection against Cross Site Request Forgeries [CSRF]. The @rsub operators can inject a token on every form (and/or other html elements). ModSecurity can store the expected token value as a variable which is compared to the value posted via forms or other html elements. ModSecurity rules can be based on request methods and URIs etc – alongside the ability to chain rules there are a huge number of options for mitigating XSS and CSRF without impacting normal applicatioin usage.

@rsub

Requirements:

  • SecRuleEngine On
  • SecRequestBodyAccess On
  • SecResponseBodyAccess On

## To enable @rsub

  • SecStreamOutBodyInspection On
  • SecStreamInBodyInspection On
  • SecContentInjection On

Injecting unique request id from mod_unique_id into forms:

SecRule STREAM_OUTPUT_BODY "@rsub s/<\/form>/<input type=\"hidden\" name=\"rv_token\" value=\"%{unique_id}\"><\/form>/" \
"phase:4,t:none,nolog,pass"

Some simple rules:

<LocationMatch ".*\/<directory requiring authentication>\/.*">
# All requests submitted using POST require a token - not the validation of the token can only be completed if that variable is stored from a previous response
SecRule REQUEST_METHOD "^(?:POST)$" "chain,phase:2,id:'1234',t:none,block,msg:'CSRF Attack Detected - Missing CSRF Token when using POST method - ',redirect:/" SecRule &ARGS:token "!@eq 1" "setvar:'tx.msg=%{rule.msg}',setvar:tx.anomaly_score=+%{tx.critical_anomaly_score},setvar:tx.%{rule.id}-WEB_ATTACK/CSRF-%{matched_var_name}=%{matched_var}"
# Check referrer is valid for an authenticated area of the application

SecRule REQUEST_HEADERS:Referer "!@contains <my website>" "block,phase:2,id:'2345',t:none,block,msg:'CSRF Attack Detected - No external referers allowed to internal portal pages',redirect:/" SecRule REQUEST_URI "@contains confirmUpdate" "chain,phase:2,id:'3456',t:none,block,msg:'CSRF Attack Detected - Missing CSRF Token. Confirmation button - ',redirect:/" SecRule &ARGS:rv_token "!@eq 1" "setvar:'tx.msg=%{rule.msg}',setvar:tx.anomaly_score=+%{tx.critical_anomaly_score},setvar:tx.%{rule.id}-WEB_ATTACK/CSRF-%{matched_var_name}=%{matched_var}" </LocationMatch>

Pros:

  • Wide capabilities for logging, alerts, blocking, redirecting, transforming
  • Parses everything coming into your web server over HTTP
  • Virtual patching – if a vulnerability is made public that affects your web application you can write and deploy a rule to mitigate the vulnerability much faster than re-release of application code patched
  • Extended uses – the capabilities of ModSecurity can be applied to applications outside the scope of application security

Cons:

  • Added complexity to your application delivery chain – another point for maintenance and failure
  • Performance costs? – Though I have not had the opportunity to test the performance costs holding session information in memory and inspecting every byte of HTTP traffic can’t be free from performance cost
  • Hardware costs – Particularly if using ModSecurity’s BodyAccess and BodyInspection features, memory usage will be significant

Improving deployments:

  • Starting off being aggressive on warnings and very light on action is a necessity to ensure no impact on normal application usage
  • From this point rules and actions need to be refined
  • Understanding how the applications works allows the use of ModSecuirtys header and body inspection in effective ways

Some other notes extracted from the ModSecurity Handbook – If you decide to use ModSecurity I strongly recommend buying the handbook. It is not expensive and saves a lot of time.

### RULE STRUCTURE ###
SecRule VARIABLES OPERATOR [TRANSFORMATION_FUNCTIONS, ACTIONS]

### VARIABLES ###
REQUEST_URI Request URI, convert to exclude hostname
REQUEST_METHOD Request method
ARGS Request parameters (read-only collection)
ARGS_NAMES Request parameters’ names (collection)
ARGS_GET Query string parameters (read-only collection)
ARGS_GET_NAMES Query string parameters’ names (read-only collection)
ARGS_POST Request body parameters (read-only collection)
ARGS_POST_NAMES Request body parameters’ names (read-only collection)
### STRING MATCHING OPERATORS ###
@beginsWith Input begins with parameter
@contains Input contains parameter
@endsWith Input ends with parameter
@rsub Manipulation of request and response bodies
@rx Regular pattern match in input
@pm Parallel pattern matching
@pmFromFile (also @pmf as of 2.6) Parallel patterns matching, with patterns read from a file
@streq Input equal to parameter
@within Parameter contains input
### NUMBER MATCHING OPERATORS ###
@eq Equal
@ge Greater or equal
@gt Greater than
@le Less or equal
@lt Less than
### ACTIONS ###
# DISRUPTIVE
allow Stop processing of one or more remaining phases
block Indicate that a rule wants to block
deny Block transaction with an error page
drop Close network connection
pass Do not block, go to the next rule
pause Pause for a period of time, then execute allow.
proxy Proxy request to a backend web server
redirect Redirect request to some other web server
# FLOW
chain Connect two or more rules into a single logical rule
skip Skip over one or more rules that follow
skipAfter Skip after the rule or marker with the provided ID
Others..
#METADATA, #VARIABLE, #LOGGING, #SPECIAL, #MISC
Categories
Random

SSL Review part 1

Most of us use and rely on SSL everyday. The mathematical workings of the RSA [Rivest, Shamir, Adleman] algorithm are not overly complex but mapping everything back to what happens in reality requires detailed understanding. Skipping over the need for SSL (for confidential and authenticated exchange of a symmetric key over and insecure medium) I will review the mathematical workings then how they are applied in real world examples.

There are also details in previous posts – RSA1, RSA2

Mathematics 

Step
Components
1. public key – e
standard practice to choose: 65537 
2. random primes p,q
Let’s use:

579810099525248565010050509754571001027,

6989752565699505597485398979958574481969

3. key modulus – n
 n = pq:

4052729130775091849638047446256554071699019514021047339267026030072286291982163

4. φ(n) = (p – 1)(q – 1)
 φ(n):

4052729130775091849638047446256554071691449951355822585104530580582573146499168

5. find e that is co-prime with φ(n)
 already using a prime,which will be co- prime.. – e = 65537 (in binary 10000000000000001)
6. (ed) mod φ(n) = 1d = e–1 mod φ(n) –  Modular multiplicative inverseMore than one answer
using Extended Euclidean algorithm:

944402082567056818708092537028397604145319798848072425038015030084640082599681,

4997131213342148668346139983284951675836769750203895010142545610667213229098849,

..+ 2φ(n), +3φ(n))

7. private key – d
 de–1 mod φ(n):

944402082567056818708092537028397604145319798848072425038015030084640082599681

With a public key (e), a key modulus (n) and a private key (d) we can apply the RSA algorithm.

Message (mess) = 911

RSA encrypt -> mess ^ e mod n  = 911 ^65537 mod 4052729130775091849638047446256554071699019514021047339267026030072286291982163

RSA encrypted message (ciph) = 3095021178047041558314072884014000324030086129008597834642883051983162360819331

RSA decrypt -> ciph ^ d mod n = 3095021178047041558314072884014000324030086129008597834642883051983162360819331 ^ 944402082567056818708092537028397604145319798848072425038015030084640082599681 mod

4052729130775091849638047446256554071699019514021047339267026030072286291982163

= 911

How is that secure?

When Alice encrypts using Bob’s public key (e) along with the key modulus (n) the output is a protected cipher.

An eavesdropper does not know the private key so decryption is very difficult:

Attacker must solve:

(unknown val, x) ^ e mod n = ciph

x ^65537 mod 4052729130775091849638047446256554071699019514021047339267026030072286291982163 = 3095021178047041558314072884014000324030086129008597834642883051983162360819331

OR, easier – try to determine the private key:

The attacker knows e and n (which = pq). When we created the private key (step 6 above) we conducted:  e–1 mod φ(n) – Modular multiplicative inverse which is relatively fast for us to calculate.

The attacked does not know  e–1 mod φ(n) though. φ(n) = (p – 1)(q – 1). The attacker knows that n is a composite prime = pq (where p and q are both primes).

So… if the attacker can solve p * q = n (where they know n) then RSA is insecure.

Thankfully the process of Integer factorization is so much harder than the process of creating p,q,nφ(n), e and d that online business and confidentiality can be maintained to acceptable levels.

Threats to RSA

It would be extremely valuable to malicious individuals/groups and  (more importantly) intelligence organizations make large integer factorization efficient enough to break RSA.

However the theoretical aspects of RSA are not generally recognized as the main source of vulnerability

Categories
Data Mining Project

Week 3 – Introduction to R. Cont’

Coming back to R after closing, a session can be restored by simply running R in the workspace directory.

A history file can be specified via:

# recall your command history 
loadhistory(file="myfile") # default is ".Rhistory"

RData can also be saved and loaded via:

# save the workspace to the file .RData in the cwd 
save.image()

# save specific objects to a file
# if you don't specify the path, the cwd is assumed 
save(object list,file="myfile.RData")
# load a workspace into the current session
# if you don't specify the path, the cwd is assumed 
load("myfile.RData")

Describing data:

# show data files attached
ls()
# show dimensions of  a data object 'd'
dim(d)
#show structure of data object 'd'
str(d)
#summary of data 'd'
summary(d)

Subsets of data is a logical next step:

summary(subset(d, read <= 60))

Grouping data is also fairly intuitive:

by(d[, 7:11], d$prog, colMeans)
by(d[, 7:11], d$prog, summary)

Using histograms to plot variable distributions:

ggplot(d, aes(x = write)) + geom_histogram()
# Or kernel density plots
ggplot(d, aes(x = write)) + geom_density()
# Or boxplots showing the median, lower and upper quartiles and the full range
ggplot(d, aes(x = 1, y = math)) + geom_boxplot()

Lets look at some more ways to understand the data set:

# density plots by program type
ggplot(d, aes(x = write)) + geom_density() + facet_wrap(~prog)
# box plot of math scores for each teaching program
ggplot(d, aes(x = factor(prog), y = math)) + geom_boxplot()

Extending visualizations:

ggplot(melt(d[, 7:11]), aes(x = variable, y = value)) + geom_boxplot()
# break down by program:
ggplot(melt(d[, 6:11], id.vars = "prog"), aes(x = variable, y = value, fill = factor(prog))) +  geom_boxplot()

Analysis of categories can be conducted with frequency tables:

xtabs(~female, data = d)
xtabs(~race, data = d)
xtabs(~prog, data = d)
xtabs(~ses + schtyp, data = d)

Finally lets have a look at some bivatiate (pairwise) correlations. If ther is no missing data, cor function can be users, else use can remove items:

cor(d[, 7:11])
ggpairs(d[, 7:11])

 

Categories
Data Mining Project

Week 2 – Introduction to R.

Why use R?

R is an integrated suite of software facilities for data manipulation, calculation and graphical display. – http://cran.csiro.au/doc/manuals/r-release/R-intro.html

This is a valid question considering that most languages/frameworks, including CUDA have statistical analysis libraries built in. Hopefully running through some introductory exercises will reveal the benefits.

Associated GUI’s and extensions:

  • Weka – Specific for machine learning algorithms
  • R Commander – Data analysis GUI

Install on Ubuntu 12.04:

  1. sudo echo "deb http://cran.csiro.au/bin/linux/ubuntu precise/" >> /etc/apt/sources.list
    sudo apt-get update
    sudo apt-get install r-base

    Then to enter the R command line interface, $ R

    For starters, will run through an intro from UCLA: http://www.ats.ucla.edu/stat/r/seminars/intro.htm

    Within the R command line interface if a package is to be used it must first be installed:

    install.packages()
    • foreign – package to read data files from other stats packages
    • xlsx – package (requires Java to be installed, same architecture as your R version, also the rJava package and xlsxjars package)
    • reshape2 – package to easily melt data to long form
    • ggplot2 – package for elegant data visualization using the Grammar of Graphics
    • GGally – package for scatter plot matrices
    • vcd – package for visualizing and analyzing categorical data
    install.packages("xlsx")
    install.packages("reshape2")
    install.packages("ggplot2")
    install.packages("GGally")
    install.packages("vcd")

    Pre-requisites:

    sudo apt-get install openjdk-7-*
    sudo ln -s /usr/lib/jvm/java-7-openjdk-amd64/bin/java /etc/alternatives/java
    sudo R CMD javareconf

    Preparing session:

    After installing R and the packages needed for a task if these packages are needed in the current session they must be included:

    require(foreign)
    require(xlsx)

    After attaching all of the required packages to the current session, confirmation can be completed via:

    sessionInfo()

    R code can be entered into the command line directly or saved to a script which can be run inside a session using the ‘source’ function.

    Help can be attained using ? preceding a function name.

    Entering Data:

    R is most compatible with datasets stored as text files, ie: csv.

    Base R contains functions read.table and read.csv see the help files on these functions for many options.

    # comma separated values
    dat.csv <- read.csv("http://www.ats.ucla.edu/stat/data/hsb2.csv")
    # tab separated values
    dat.tab <- read.table("http://www.ats.ucla.edu/stat/data/hsb2.txt", header=TRUE, sep = "\t")
    

    Datasets from other statistical analysis software can be imported using the foreign package:

    require(foreign)
    # SPSS files
    dat.spss <- read.spss("http://www.ats.ucla.edu/stat/data/hsb2.sav", to.data.frame=TRUE)
    # Stata files
    dat.dta <- read.dta("http://www.ats.ucla.edu/stat/data/hsb2.dta")

    If converting excel spreadsheets to CSV is too much of a hassle the xlxs package we imported will do the job:

    # these two steps only needed to read excel files from the internet
    f <- tempfile("hsb2", fileext=".xls")
    download.file("http://www.ats.ucla.edu/stat/data/hsb2.xls", f, mode="wb")
    dat.xls <- read.xlsx(f, sheetIndex=1)

    Viewing Data:

    # first few rows
    head(dat.csv)
    # last few rows
    tail(dat.csv)
    # variable names
    colnames(dat.csv)
    # pop-up view of entire data set (uncomment to run)
    View(dat.csv)
    

    Datasets that have been read in are stored as data frames which have a matrix structure. The most common method of indexing is object[row,column] but many others are available.

    # single cell value
    dat.csv[2, 3]
    # omitting row value implies all rows; here all rows in column 3
    dat.csv[, 3]
    # omitting column values implies all columns; here all columns in row 2
    dat.csv[2, ]
    # can also use ranges - rows 2 and 3, columns 2 and 3
    dat.csv[2:3, 2:3]

    Variables can also be accessed via their names:

    # get first 10 rows of variable female using two methods
    dat.csv[1:10, "female"]
    dat.csv$female[1:10]

    The c function is used to combine values of common type together to form a vector:

    # get column 1 for rows 1, 3 and 5
    dat.csv[c(1, 3, 5), 1]
    ## [1]  70  86 172
    # get row 1 values for variables female, prog and socst
    dat.csv[1, c("female", "prog", "socst")]
    ##   female prog socst
    ## 1      0    1    57

    Creating colnames:

    colnames(dat.csv) <- c("ID", "Sex", "Ethnicity", "SES", "SchoolType", "Program", 
        "Reading", "Writing", "Math", "Science", "SocialStudies")
    
    # to change one variable name, just use indexing
    colnames(dat.csv)[1] <- "ID2"

    Saving data:

    #write.csv(dat.csv, file = "path/to/save/filename.csv")
    #write.table(dat.csv, file = "path/to/save/filename.txt", sep = "\t", na=".")
    #write.dta(dat.csv, file = "path/to/save/filename.dta")
    #write.xlsx(dat.csv, file = "path/to/save/filename.xlsx", sheetName="hsb2")
    # save to binary R format (can save multiple datasets and R objects)
    #save(dat.csv, dat.dta, dat.spss, dat.txt, file = "path/to/save/filename.RData")
    #change workspace directory
    setwd("/home/a/Desktop/R/testspace1")
Categories
Random

downloading a youtube playlist and converting to mp3 (osx/linux(ubuntu))

Downloading youtube audio and converting mp3 is very simple now thanks to these guys: https://rg3.github.io/youtube-dl/

Installing:

# on Ubuntu
sudo apt-get install youtube-dl avconv
curl https://raw.githubusercontent.com/SecurityShift/tools/master/scripts/random/GetYoutubePlaylist.sh -o GetYoutubePlaylist.sh
chmod 755 GetYoutubeAudio.sh

https://raw.githubusercontent.com/SecurityShift/tools/master/backup_scripts/google_drive_backup.py

# on OSX
brew install youtube-dl libav
curl https://raw.githubusercontent.com/SecurityShift/tools/master/scripts/random/GetYoutubePlaylist.sh -o GetYoutubePlaylist.sh
chmod 755 GetYoutubeAudio.s

Contents:


Usage: sh GetPlaylist.sh [youtube playlist URL] [output_directory]

Example:

sh ./GetYoutubePlaylist.sh http://www.youtube.com/playlist?list=PL702CAF4AD2AED35B ~/Music

To get the youtube playlist URL view the playlist by clicking on its name, no videos will be playing, then click on share and the url will be highlighted:

youtube-playlist
click on share and the URL will appear
Categories
Random

content private

content private

Categories
Introduction to Parallel Programming Online Courses

Introduction to Parallel Programming – Week 5 Part 2

Week 5 -> Optimizing GPU Programs (continued)

Goal: Maximize useful computation/second

After walking through APOD [Analyze, parallelize, optimize, deploy] the lecture turned to memory bandwidth. Using the CUDA utility deviceQuery to calculate memory bandwidth using memory clock rate and memory bus width.

After determining the maximum theoretical bandwidth at 40 Gb/s practical goals were set:

  • 40-60% -> OK
  • 60-75% -> good
  • >75% -> excellent
Using 12.5 GB/s of memory bandwidth is under utilizing!
Using 12.5 GB/s of memory bandwidth is under utilizing!

The algorithm being analyzed is a transpose. When DRAM utilization is low the first guess should be lack of coalescing.

In our example code we find that the reading of memory is well coalesced.. but the writing phase is strided by N elements (1024). This was described as ‘bad’.

So considering that most GPU codes are memory limited checking memory bandwidth utilization is very important.

Enter a tool – nSightm nvpp [nvidia visual profiler]  – confirms that the write to memory operations are utilizing very little memory bandwidth whilst the read  operations are at 100% utilization.

The solution for this algorithm is ’tiling’. Tiling utilizes shared memory, taking a tile of the input copying and transposing into output. The code for this solution can be found here: https://github.com/udacity/cs344/blob/master/Unit5%20Code%20Snippets/transpose.cu

Occupancy – Each SM has a limited number of:

  • Thread blocks -> 8
  • Threadss -> 1536/2048
  • registers for all threads -> 65536
  • bytes of shared memory 16K-48K

Maximizing number of threads on the SM [streaming multi processor] will maximize occupancy. The limits for specific hardware can be found via deviceQuery.

The transpose code was further optimized, better versions can be seen in the link above.

Shared memory bank conflicts ->organized into banks and depending on how threads access memory in tile, replays of shared memory accesses can occur. (ie: striping shared memory usage across banks).

Referring back to the goal of maximizing effective computation we have just address one factor:

  • minimize time waiting at barriers

The next to be address was:

  • minimize thread divergence

Some important definitions:

  • warp – set of threads that execute the same instruction at a time
  • SIMD – Single instruction, multiple data (CPU
  • SIMT – Single instruction, multiple thread

Thread divergence is can result in up to 32x slower code. Warps on nvidia hardware have 32 threads which apply single instruction to multiple threads.

Next topic was Streams, launching kernels in separate streams allows for concurrent execution:

cuda_streams
Benefits of specifying CUDA streams

To create streams:

cudaSteam_t s1;

cudaStreamCreate(&s1);

cudaStreamDestroy(s1);

asynchronous memory transfer  – cudaMemcpyAsync – called on pinned memory.

Week 5 lectures

Week 5 code – failed to get shared memory working even with atomicAdd 🙁

Categories
Functional Programming - Scala Random

Virtual Enigma Machine Implementation

After watching a video on numberphile thought it would be interesting to implement a virtual version on the Enigma cipher machine.

Step 1: Install Scala and Eclipse IDE for Scala.

http://www.scala-lang.org/downloadshttp://scala-ide.org/

Step 2: Review the numberphile video and how the Enigma machine works

Step 3: Implement each function of the machine

  1. Rotors
    • Rotor choices, rotors have different circuitry (0-24) – static value for each message
    • Initial rotor combination (0-25) – static value for each message
    • Rotor increment – Faster rotor, middle rotor, slow rotor
  2. Plug board
    • 10 wires
    • swapping 2 letters
    • static value for each message

Step 4: Write an interface between the functions and a basic interface (text?)

Step 5: Test!

Conclusion: Using Scala (trying anyway) the implementation is not very complex. What is more difficult is replicating the original machines where the output character could not equal the input character. The limitation Turing used to crack the machines. Might see if I can implement that later then test out the cracking method. Not sure how easy it would be to break the current implementation…

CODE (EnigmaMachine.scala, EnigmaMachine.class):

 

 

// Virtual reconstruction of what the enigma machines did
// The replication is of the improved version where the input could result in the same output

object EnigmaMachine {
//////////////// ENCRYPTION/DECRYPTION FUNCTIONS \\\\\\\\\\\\\\\\\\\\\
    //to replicate the simple machine circuit chars are converter to 0 - 25
    def convertMessageToSimpleInt(rawInput: String):List[Int] = {
        val userMessage = rawInput.toUpperCase
      (for (x <- userMessage) yield if (x != 32) (x.toInt - 65) else 26).toList
    }
    
    //for all integers in the list, convert
    def convertMessageToString(input: List[Int]): String = {
      (for (x <- input) yield if (x == 26) " " else (x + 65).toChar).mkString
    } 
    
    def enigmaGo(rotorChoices: List[Int], rotorPositions: List[Int], inputMessage: List[Int], encrypt: Boolean): List[Int] = {    
      // incrementing the rotors is dont based on the number of previous chars.. instead of the previous position
      def incrementRots(nth: Int): List[Int] = {
        val rot0 = (rotorPositions(0) + nth) % 26 //fast rotor
        val rot1 = (rotorPositions(1) + (nth / 26)) % 26 //medium rotor
        val rot2 = (rotorPositions(2) + ((nth / 26) /26)) % 26 //slow rotor
        List(rot0, rot1, rot2)
      }
      //applies the rotor encryption then the scramble board
      def transmuteElement(element: Int, rotPosApp: List[Int]): Int = {
        val rotorTotal = rotorList(rotorChoices(0))(rotPosApp(0)) +
              rotorList(rotorChoices(1))(rotPosApp(1)) +
              rotorList(rotorChoices(2))(rotPosApp(2)) 
        
      def scramble(inputVal:Int):Int = plugMap1.find(x => (x._1 == inputVal) || (x._2 == inputVal)) match {
            case Some(y) => if (y._1 == inputVal) y._2 else y._1 
          case None => inputVal
      }
        if (element == 26) element
        else if (encrypt) (scramble(element) + rotorTotal) % 26 else { 
            //decrypt is a bit messy atm :( 
            if (element - (rotorTotal % 26) < 0) scramble(element - (rotorTotal % 26) + 26) else scramble(element - (rotorTotal % 26))
          }     
      }
      
      //Accumulator hold the input and output lists, when input list is empty, return output.. also tail recursive
      def enigmaAccu(remInput: List[Int], rotPos: List[Int], accumOutput: List[Int]): List[Int] = {
              if (remInput.isEmpty) accumOutput
            else enigmaAccu(remInput.tail, incrementRots(accumOutput.length), accumOutput:+(transmuteElement(remInput.head, rotPos)))
      }
      
      enigmaAccu(inputMessage, rotorPositions, Nil) //start the process
    }
////////////////////   \\\\\\\\\\\\\\\\\\\\\\\\\
    
//////////////// UI STUFF \\\\\\\\\\\\\\\\\\\\\
    def useMachine(rotorChoices: List[Int], rotorStartVals: List[Int], activity: String) = {
            spamLine
            val inputMessage = convertMessageToSimpleInt(askInput("Please enter a message to be " + activity + ", use only a-z: "))
            val resultingMessage = enigmaGo(rotorChoices, rotorStartVals, inputMessage, if (activity == "encrypted") true else false)
            spamLine
            println("Your message has been " + activity + ": ")
        println(convertMessageToString(resultingMessage))
            spamLine
            exit(0)
    }

    def getRotorChoices(s1:String, p: String => Boolean):List[Int] = {
        val slot0 = getUserInput(s1 + "fast slot: ", "Entry Invalid.", p).mkString
        val slot1 = getUserInput(s1 + "medium slot: ", "Entry Invalid.", p).mkString
        val slot2 = getUserInput(s1 + "slow slot: ", "Entry Invalid.", p).mkString
        List(slot0.toInt,slot1.toInt,slot2.toInt)
    }
    
    def spamLine = println("##############################################")
    
    def askInput(statement: String) = { 
      val input = readLine(statement)
      if (input == "") "99" else input
    }
    
    def askAgain(statement: String, f: => String) = {
        println(statement)
        f
    } 
    
    def inputVals(f1: => String, f2: => String) = Stream.cons( f1, Stream.continually(f2))
    
    def getUserInput(s1: String, s2: String, p:String => Boolean) = inputVals(askInput(s1), askAgain(s2, askInput(s1))).find(p)
////////////////////   \\\\\\\\\\\\\\\\\\\\\\\\\
    
//////////////// MAIN \\\\\\\\\\\\\\\\\\\\\ 
        def main(args: Array[String]) {
            println("### WELCOME TO THE ENIGMA MACHINE! ###" )
            // GET INITIAL MACHINE SETTINGS FROM USER 
            // ROTOR PLACEMENT CONFIG
            val rotorChoices = getRotorChoices("Choose rotor (0 - 4) for ", x => (x.toInt >= 0 && x.toInt < 5)) 
            // ROTOR START VALS 
            val rotorStartVals =  getRotorChoices("Choose rotor START VAL (0 - 25) for ", x => (x.toInt >= 0 && x.toInt < 25))
            // PLUG MAP
            println("There is only 1 plug map option at present:") 
            println(plugMap1.toString.drop(4))
            //ENCRYPT OF DECRYPT - ONLY RELEVENT FOR GUI TEXT.. bleh not quite need to reverse circuit manually
            val userChoice = getUserInput("Press 1 to encrypt, 2 to decrypt: ", "Entry Invalid.", x => (x == "2" || x == "1"))
            userChoice.mkString match {
              case "1" => useMachine(rotorChoices, rotorStartVals, "encrypted") 
              case "2" => useMachine(rotorChoices, rotorStartVals, "decrypted")
              case default => exit(0)
            }
    }
////////////////////   \\\\\\\\\\\\\\\\\\\\\\\\\

//////////////// CONSTANTS \\\\\\\\\\\\\\\\\\\\\
    val rotorList = List(List(6, 17, 4, 3, 23, 22, 21, 5, 0, 19, 20, 11, 16, 9, 13, 24, 18, 1, 8, 2, 7, 10, 12, 14, 25, 15)
    ,List(2, 7, 23, 12, 13, 15, 18, 1, 8, 11, 0, 3, 10, 5, 24, 4, 17, 19, 6, 9, 20, 14, 25, 21, 16, 22)
    ,List(23, 1, 19, 18, 0, 10, 3, 8, 9, 21, 2, 12, 13, 14, 24, 6, 20, 16, 11, 17, 15, 7, 4, 25, 22, 5)
    ,List(21, 22, 16, 2, 18, 20, 15, 9, 5, 1, 17, 10, 3, 6, 0, 13, 11, 23, 4, 12, 19, 8, 7, 25, 24, 14)
    ,List(25, 3, 11, 7, 5, 15, 24, 10, 21, 6, 12, 17, 8, 23, 2, 18, 19, 14, 4, 0, 20, 9, 22, 1, 16, 13))
    
    val plugMap1 = List((3,7),(11,16),(18,24),(17,9),(21,19),(14,13),(0,12),(1,25),(22,20),(4,6))
////////////////////   \\\\\\\\\\\\\\\\\\\\\\\\\
}
Categories
Introduction to Parallel Programming Online Courses

Introduction to Parallel Programming – Week 5 Part 1

Week 5 -> Optimizing GPU Programs.

Parallelizing and porting programs to run on CUDA is generally done to either solve bigger problems or to solve more problems. So optimizing programs to require less time may be beneficial.

It is important to note that optimization should be completed with reference to the goals of the program and the execution time of each part of the program. Once a function is no longer a performance bottle neck the returns on further optimization are likely to be diminished.

#### BASIC PRINCIPLES OF EFFICIENT GPU PROGRAMMING ####
– decrease time spent on memory operations
– coalesce global memory access
– avoid thread divergence

These basic principles do have exceptions. For instance, the transfer of data from global to shared memory may increase time on memory operations but decrease overall execution time.

The lecture highlighted some types of optimization:

  1. Selecting the right algorithm -> Likely to have the largest impact
  2. Applying the basic principles for efficiency
  3. Architecture specific optimizations
  4. Micro optimizations (instruction level)

A methodology for the development process of parallel applications was subsequently suggested:

  1. Analyze -> Profile the applications identifying bottlenecks/hotspots
  2. Parallelize -> using approaches such as libraries/OpenMP/CUDA, also selecting algorithms
  3. Optimize -> Measurement focus
  4. Deploy -> Optimization should not be completed in a vacuum it is too difficult to predict and emulate real usage

[APOD]

A simple working example on optimizing the transposing matrices followed.

Timing the function from a standard serial implementation to moderately parallel example and finally implementing our own fully parallel code. The code for the example: week5_example1.cu

Focusing too much on a single function will generally yield diminishing returns
Focusing too much on a single function will generally yield diminishing returns