Month: October 2014

Natas Level 15 → Level 16

The page contain a username for you to check if the user exist. Looking at the source code, we can see there is a very similar attack to use from our sql injection from previous level

<? 

/* 
CREATE TABLE `users` ( 
  `username` varchar(64) DEFAULT NULL, 
  `password` varchar(64) DEFAULT NULL 
); 
*/ 

if(array_key_exists("username", $_REQUEST)) { 
    $link = mysql_connect('localhost', 'natas15', '<censored>'); 
    mysql_select_db('natas15', $link); 
     
    $query = "SELECT * from users where username=\"".$_REQUEST["username"]."\""; 
    if(array_key_exists("debug", $_GET)) { 
        echo "Executing query: $query<br>"; 
    } 

    $res = mysql_query($query, $link); 
    if($res) { 
    if(mysql_num_rows($res) > 0) { 
        echo "This user exists.<br>"; 
    } else { 
        echo "This user doesn't exist.<br>"; 
    } 
    } else { 
        echo "Error in query.<br>"; 
    } 

    mysql_close($link); 
} else { 
?>

Notice that this time, it only check for the username and return only two response, either the user exists or not. However, from our last sql injection, we can see that this code is still not sanitizing the double quote which mean we can input what in the first line below into the user input form to include the criteria for password (see the previous level) and create query like the second line

X" and password = "X
SELECT * from users where username = "X" and password = "X"
However, the response is only the user exist or not. Therefore, we need to find the username and then find out what the password. From our previous levels, we know this time we are looking for user natas16 password. If we just try that username, the user exist! Next, if you remember, all of the password for each level are 32 characters. One way to find out if this is true is to use the sql LIKE and wildcard to check the user still exist if we put the following input.
natas16" and password like "________________________________
Indeed, we put 32 “_” characters and the user still exist but not with 33 because “_” is a wildcard for a single character. Now, instead of putting 32 “_”, we put a% at the end where % is wildcard for any number of any character, we can check to see if the first character start with a. If you try this up to w, it will produce the user exist response but W also works. The reason is that upper and lower case are not distinguish. Therefore, after “like”, we put “binary” before W%” to make sure this is case sensitive. Obviously, doing this 32 times is a bit too much. So I got a python script to do exactly that. After we run our program for a while, the next password is shown at the end.
WaIHEacj63wnNIBROHeqi3p9t0m5nhmh

Beside using like, regexp is also possible to use in sql. However, the wildcard characters are different. Finally, Burp, the tool that we have been using to intercept our traffic has a function call Intruder where you can set your payload to brute forcer and do exactly the python script does for each characters.

Additional resources:

Advertisements

Problem 10

99 Haskell Problems

Problem 10

(*) Run-length encoding of a list. Use the result of problem P09 to implement the so-called run-length encoding data compression method. Consecutive duplicates of elements are encoded as lists (N E) where N is the number of duplicates of the element E.

Example:

* (encode '(a a a a b c c a a d e e e e))
((4 A) (1 B) (2 C) (2 A) (1 D)(4 E))

Example in Haskell:

encode "aaaabccaadeeee"
[(4,'a'),(1,'b'),(2,'c'),(2,'a'),(1,'d'),(4,'e')]

Solution:

encode :: Eq a => [a] -> [(Int, a)]
encode [] = []
encode x = encodePack (pack x)
encodePack [] = []
encodePack (x:xs) = (length x, head x):encodePack xs

Note: The type signature of encode return a list of tuple (Int, a) as defined.

Use of list comprehension or lambda with map function can shorten the solution. The list comprehension describe the mathematics of creating the list of tuple by taking an element x from the list (pack xs) and use x to create the element of the tuple (length x, head x). The lambda function (\x -> (length x, head x)) take an argument of a list and turn it into a tuple. The map function map this lambda function to each element of (pack xs).

encode xs = [(length x, head x) | x <- pack xs]
encode xs = map (\x -> (length x, head x)) (pack xs)

Problem 09

99 Haskell Problems

Problem 9

(**) Pack consecutive duplicates of list elements into sublists. If a list contains repeated elements they should be placed in separate sublists.

Example:

* (pack '(a a a a b c c a a d e e e e))
((A A A A) (B) (C C) (A A) (D) (E E E E))

Example in Haskell:

*Main> pack ['a', 'a', 'a', 'a', 'b', 'c', 'c', 'a', 
             'a', 'd', 'e', 'e', 'e', 'e']
["aaaa","b","cc","aa","d","eeee"]

Solution:

pack [] = []
pack [x] = [[x]]
pack (x:xs)
  | elem x (head (pack xs)) = (x:head (pack xs)):tail (pack xs)
  | otherwise = [x]:pack xs

This solution check if x is an element of xs where x is the head of the list and xs is the tail. If x is not in xs (otherwise condition), then x becomes a list itself. Since we pack xs first, we recurse to the last element and build the list of list from there.

Note: Again the signature of pack must be a list of element that can be compare equality

:t pack
pack :: Eq a => [a] -> [[a]]

Chapter 6: Syntax

6.1 Lexical Structure of Programming Languages

  • Token categories
    • reserved words (keywords)
    • literals or constants
    • special symbols
    • identifiers
  • principle of longest substring takes the longest possible substring of nonblank characters as a single token.
  • Regular expression
    • + mean one or more
    • ? mean one or none
    • * mean none or more

6.2 Context-Free Grammars and BNF’s

  • Elements of CFG
    • start symbol is nonterminal that stands for the entire, top-level phrase being defined.
    • nonterminals are broken down into further phrase structures
    • terminals cannot be broken down into further phrase structures
    • productions are rules use for the derivation.
  • CFG defines a language.

6.3 Parse Trees and Abstract Syntax Trees

  • A Parse Tree is labeled by nonterminal at interior nodes and terminals at leaves. The structure of a parse tree is completely specified by the grammar rules of the language and a derivation of a particular sequence of terminals.
  • Abstract syntax tree abstract the essential structure of the parse tree.
Example: arithmetic expression grammar
expr   → expr + expr | expr * expr | (expr) | number
number → number digit | digit
digit  → 0 | 1 | 2 | 3 | 4| 5 | 6 | 7 | 8 | 9

Example: parse tree for 234
         number
        /     \
    number    digit
   /     \      |
number  digit   4
  |       |
digit     3
  |
  2

Example: abstract syntax tree for 234
    4
   /
  3
 /
2

6.4 Ambiguity, Associativity, and Precedence

  • A grammar which two distinct parse trees are possible for the same string is ambiguous.
  • left-recursive rule for an operation causes it to left-associate, right-recursive causes right-associate.
3 + 4 + 5

left-recursive/associate
expr → expr + term

          expr
         / | \
     expr  +  term
    / | \      |
expr  +  term  5
 |        |
 3        4

right-recursive/associate
expr → term + expr

     expr
    / | \
term  +  expr
 |       / | \      
 3   term  +  expr
      |        |
      4        5

6.5 EBNFs and Syntax Diagrams

  • EBNF
    • {} stands for “zero or more repetition of”
    • [] indicate optional part of the structure

6.6 Parsing Techniques and Tools

  • Bottom-up parser match an input with the right-hand sides of the grammar rules, when match occurs, the right-hand side is replaced by, or reduced to, the nonterminal on the left.
  • Top-down parsers expand the nonterminal to match incoming tokens and directly construct a derivation.
  • Recursive-decent parser turns the nonterminals into a group of mutually recursive procedures whose actions are based on the right-hand sides of the BNF’s.
  • predictive parser requirement
    • able to distinguish between choices in a grammar rule in term of First sets or the First sets of any two choices must not have any token in common (where First(\alpha) to be the set of tokens that can begin the string \alpha).
    • for any optional part, no token beginning the optional part an also come after the optional part.

6.7 Lexics vs. Syntax vs. Semantics

6.8 Case Study: Building a Syntax Analyzer for TinyAda

Additional Notes

Exercise

Other Resources

Chapter 7: Modules

Learn You a Haskell for Great Good!

Loading modules

  • Modules is a collection of related functions, types and typeclasses.
  • Prelude module is imported by default.
import <module name>
  • nub is a function defined in Data.List that take a list and weeds out duplicate elements.
  • The following are equivalent
length.nub
\xs -> length (nub xs)
  • To import module in GHCI (interpreter), use
:m + Data.List Data.Map Data.set
  • To use, or hide a specific function.
import Data.List (nub, sort)
import Data.List hiding (nub)
  • To resolve conflict in namespace, use qualified to ensure that import module still need to use the module name to call each function such as
import qualified Data.Map
Data.Map.filter
import qualified Data.Map as M
M.filter

Data.List

  • Data.List module contain function about List.
  • intersperse take an element and a list and then puts that element in between each pair of element in the list.
intersperse '.' "MONKEY"
"M.O.N.K.E.Y"
  • intercalate takes a list of lists and a list and inserts the list in between the list of lists and flatten the list of lists.
intercalate [0,0] [[1,2],[3,4],[5,6]]
[1,2,0,0,3,4,0,0,5,6]
  • transpose transposes a list of lists like a 2D matrix.
  • concat flatten a list of lists into a list of elements.
  • The following are equivalent
concat (map (replicate 4) [1..3])
concatMap (replicate 4) [1..]
  • and, or follow the predicate logic
  • any and all take a predicate and then check if any or all the elements in a list satisfy the predicate.
  • iterate take a function and a starting value and applies the function to the starting value and then apply the function to the result and use the result as new starting value
take 10 $ iterate (*2) 1
[1,2,4,8,16,32,64,128,256,512]
  • splitAt takes a number and a list. it split the list at the element corresponding to the position of the number.
  • takeWhile takes elements from a list while the predicate holds and then when an element is encountered that does satisfy the predicate, it cuts off.
  • dropWhile is opposite of takeWhile
  • span return a pair of lists where the first list is the same if use takeWhile and the second list is what would’ve dropped.
  • break p is the equivalent of doing span(not.p)
splitAt 3 "heyman"
("hey","man")
takeWhile (>3) [6,5,4,3,2,1,2,3,4,5,4,3,2,1]
[6,5,4]
dropWhile (>3) [6,5,4,3,2,1,2,3,4,5,4,3,2,1]
[3,2,1,2,3,4,5,4,3,2,1]
span (>3) [6,5,4,3,2,1,2,3,4,5,4,3,2,1]
[[6,5,4],[3,2,1,2,3,4,5,4,3,2,1]]
  • sort will sorts a list
  • group will group adjacent elements into sublist if they are equal
  • inits and tails are init and tail but recursively apply to create a list
  • isInfixOf, isPrefixOf and isSuffixOf search for a sublist within, begin or end of a list, respectively.
  • elem and notElem check if an element is or not inside a list
  • partition takes a list and a predicate and return a pair of lists where the first contain element satisfy the predicate and the other list don’t.
inits "w00t"
["", "w", "w0", "w00", "w00t"]
partition (>3) [1,3,5,6,3,2,1,0,3,7]
([5,6,7],[1,3,3,2,1,0,3])
  • Maybe type can return one or nothing.
  • find takes a list and a predicate and returns the first element that satisfy the predicate. It can return one element or nothing.
  • elemIndex return either nothing or the position of the first element found.
  • elemIndices is like elemIndex but return all matching indices.
  • findIndex is like find but return the first index of the matching element. findIndices return all indices of the matching element.
  • zip and zipWith can zip together x list when using zipx and zipWithx (e.g. zip4 and zipWith4) up to x =7.
  • line takes a string and return every line of that string in a separate list
  • unlines is the inverse function of lines
  • word and unwords splitting a line of text into words or reverse the process.
  • nub take a list and take out any duplicate
  • delete take a list and an element and remove the first matching element in the list
  • \\ is a list diff function. Return a list only with different element between the lists
  • union and intersect acts exactly like set operator
  • insert take an element and a list and search for the first position that the element is smaller or equal to the next element and insert itself into that position.
insert 3 [1,2,4,3,2,1]
[1,2,3,4,3,2,1]
  • Note that length, take, drop, splitAt, !!, replicate take Int type. add generic in front to take Num type (e.g. genericSplitAt instead of splitAt)
  • nub, delete, union, intersect, group, sort, insert, maximum and minimum counterpart is add By at the end (e.g. nubBy)
  • example of using on (Data.Function), notice the first 3 negative grouped together, then the next 6 positive number, next 2 negative and finally next 2 positive values.
let value =  [-4.3, -2.4, -1.20.42.35.910.529.15.3, -2.4, -14.52.92.3]
groupBy ((==) `on` (> 0)) values
[[-4.3,-2.4,-1.2],[0.4,2.3,5.9,10.5,29.1,5.3],[-2.4,-14.5],[2.9,2.3]]  
let xs = [[5,4,5,4,4],[1,2,3],[3,5,4,3],[],[2],[2,2]]  
sortBy (compare `on` length) xs
[[],[2],[2,2],[1,2,3],[3,5,4,3],[5,4,5,4,4]]

Data.Char

  • Data.Char functions work with characters.
  • isControl checks whether a character is a control character (??)
  • isSpace, isLower, isUpper, isAlpha, isAlphaNum, isDigit, isOctDigit, isHexDigit, isLetter, isMark (unicode), isNumber, isPunctuation, isSymbol, isSeparator, isAscii, isLatin1, isAsciiUpper and isAsciiLower are self explained
  • toUpper, toLower, toTitle (title case), digitToInt and intToDigit are self explanatory as well.
  • isPrint check whether a character is printable
  • all take a predicate and a list and return True if that predicate holds for every elements in the list
all isAlphaNum "bobby283"
True
  • ord and chr convert the character to the encoding number

Data.Map

  • Data.Map function work with key-value pair list.
  • findKey takes a key and a list and filter out all non-matching key pair and first matching key-value pair.
  • fromList take an association list and return a map with the same association. The duplicate keys in the original association list are discarded. The key must be orderable.
Map.fromList [(1,2),(3,4),(3,2),(5,5)]
fromList [(1,2),(3,2),(5,5)]
  • empty represents an empty map.
  • insert takes a key, a value and a map and return a new map with those inserted into the map.
fromList' :: (Ord k) => [(k,v)] -> Map.Map k v
fromList' = foldr (\(k,v) acc -> Map.insert k v acc) Map.empty
  • null checks if a map is empty
  • size reports the size of a map
  • singleton create one mapping of a key to a value
  • lookuup returns Just something if it finds something or Nothing if not.
  • member is a predicate of whether a key and a value is in the map
  • map & filter works like list equivalents
  • toList is the inverse of fromList
  • keys and elems return list of the keys or the values, respectively.
  • fromListWith is like fromList but doesn’t discard duplicate but use the function to find out what to do with it. E.g. max (fromListWith max …) will retain the maximum value of the duplicate key.
  • insertWith is to insert what fromListWith is to fromList.

Data.Set

  • Data.Set work with set using set operators.
  • fromList functions takes a list and convert it into a set.
  • intersection, difference, union set operators work exactly like they should.
  • So is null, size, member, empty, singleton, insert and delete.
  • map and filter, toList functions also work as expected.
Set.filter odd $ Set.fromList [3,4,5,6,7,2,3,4]
fromList[3,5,7]
Set.map (+1) $ Set.fromList [3,4,5,6,7,2,3,4]
fromList [3,4,5,6,7,8]

Making our own modules

  • To make your own modules
    • create a file with a new module name (e.g. Geometry.hs)
    • Specify module name and functions at the top
    • implement each function below it
    • to use the module, use import but the module file must be in the same folder.
module Geometry
( sphereVolume
, sphereArea
, cubeVolume
, cubeArea
, cuboidArea
, cuboidVolumne
) where

sphereVolume :: Float -> Float
sphereVolume radius = (4.0 / 3.0) * pi * (radius ^ 3)
...

Other commands

  • additional explanation of fold here.
foldr (\x y -> concat ["(",x,"+",y,")"]) "0" (map show [1..5])
"(1+(2+(3+(4+(5+0)))))"
foldl (\x y -> concat ["(",x,"+",y,")"]) "0" (map show [1..5])
"(((((0+1)+2)+3)+4)+5)

Natas Level 14 → Level 15

The page contain a username and a password to be able to login. Looking at the source code, we can see that the username and password will be use as part of the sql query to obtain the authentication.

<? 
if(array_key_exists("username", $_REQUEST)) { 
 $link = mysql_connect('localhost', 'natas14', '<censored>'); 
 mysql_select_db('natas14', $link); 
 
 $query = "SELECT * from users where username=\"".$_REQUEST["username"]."\" and password=\"".$_REQUEST["password"]."\""; 
 if(array_key_exists("debug", $_GET)) { 
 echo "Executing query: $query<br>"; 
 } 

 if(mysql_num_rows(mysql_query($query, $link)) > 0) { 
 echo "Successful login! The password for natas15 is <censored><br>"; 
 } else { 
 echo "Access denied!<br>"; 
 } 
 mysql_close($link); 
} else { 
?>

We see that the first if statement check if the username exists, if so, create connection $link using mysql_connect to database natas14.

Next, the $query is constructed our of username and the password. However, the if statement under that said if there is a “debug” in our $_GET, the $query will be echo.

Lastly, it will check if the $query and the $link return more than 0 rows. If so, we get the password, otherwise, access is denied.

The key is to get the query return at least 1 row but we could return as many as we want. Let’s use the debug feature to see what the query looks like by supplying the following url.

http://natas14.natas.labs.overthewire.org/index.php?username=user&password=password&debug
Executing query: SELECT * from users where username="user" and password="password"
Access denied!
We can see that what we input in the username and password field is being use as the input for the query. A classic SQL injection is to finish the double quote and add something that is always true and match the closing double quote. Since we surrounded by double quotes, we could use something that will produce a query like this:
SELECT * from users where username="" or ""="" and password="" or ""=""
Comparing the two queries, the username and password provided in the form is shown below to match the double quote that used in the query while create an always true query.
" or ""="
After we input and hit login, the next password is shown with a successful login message.
AwWj0w5cvxrZiONgZ9J5stNVkmxdk39J

Additional resources:

Problem 041


Project Euler

Pandigital prime

Problem 41

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once. For example, 2143 is a 4-digit pandigital and is also prime.

What is the largest n-digit pandigital prime that exists?


First, the largest pandigital number is 987654321. Also, a quick way to know if a number is divisible by 3 is to see if the sum of all the digits is divisible by 3. Therefore, we can check each n-digit pandigital to see if it is possible to contain a prime.

Nay 1+2 = 3
Nay 1+2+3 = 6
Yes 1+2+3+4 = 10
Nay 1+2+3+4+5 = 15
Nay 1+2+3+4+5+6 = 21
Yes 1+2+3+4+5+6+7 = 28
Nay 1+2+3+4+5+6+7+8 = 36
Nay 1+2+3+4+5+6+7+8+9 = 45

Therefore, we should only search 4-digit and 7-digit pandigital number. Since we are looking for the largest pandigital prime, we should start the search at 7654321 and decrement the value by 2 (odd number only) until we found a number that is also a prime. By re-using the prime sieve from problem 37 and the pandigital checker from problem 38, this problem can be solve very quickly.