Both SIFT and SURF authors require license fees for usage of their original algorithms.
I have done some research about the situation and here are the possible alternatives:
Harris corner detector
Harris-Laplace - scale-invariant version of Harris detector (an affine invariant version also exists, presented by Mikolajczyk and Schmidt, and I believe is also patent free).
Multi-Scale Oriented Patches (MOPs) - athough it is patented, the detector is basically the multi-scale Harris, so there would be no problems with that (the descriptor is 2D wavelet-transformed image patch)
LoG filter - since the patented SIFT uses DoG (Difference of Gaussian) approximation of LoG (Laplacian of Gaussian) to localize interest points in scale, LoG alone can be used in modified, patent-free algorithm, tough the implementation could run a little slower
BRISK (includes a descriptor)
ORB (includes a descriptor)
KAZE - free to use, M-SURF descriptor (modified for KAZE's nonlinear scale space), outperforms both SIFT and SURF
A-KAZE - accelerated version of KAZE, free to use, M-LDB descriptor (modified fast binary descriptor)
Normalized gradient - simple, working solution
PCA transformed image patch
Wavelet transformed image patch - details are given in MOPs paper, but can be implemented differently to avoid the patent issue (e.g. using different wavelet basis or different indexing scheme)
Histogram of oriented gradients
Note that if you assign orientation to the interest point and rotate the image patch accordingly, you get rotational invariance for free. Even Harris corners are rotationally invariant and the descriptor may be made so as well.
Some more complete solution is done in Hugin, because they also struggled to have a patent-free interest point detector.
There is a relatively new method, you might want to look into:
BRISK, Binary Robust Invariant Scalable Keypoints:
In this paper we propose BRISK, a novel method for keypoint detection, description and matching. A comprehensive evaluation on benchmark datasets reveals BRISK’s adaptive, high quality performance as in state-of-the-art algorithms, albeit at a dramatically lower computational cost (an order of magnitude faster than SURF in cases). The key to speed lies in the application of a novel scale-space FAST-based detector in combination with the assembly of a bit-string descriptor from intensity comparisons retrieved by dedicated sampling of each keypoint neighborhood.
It's patent-free and free to use (as was told by the author of the algorithm).
Don't trust anyone here, talk to a lawyer. The Legal world is subtly different from ours, if I may say. Depending on what you exactly want to do (and where, etc.), there may be a solution where you could use SURF or SIFT. I have been surprised in the past how seemingly strong licenses can be overcome.
I would rather look into KAZE / AKAZE, which perform equally good with significant speed-up. The deformation cases are also tolerated. OpenCV has recently obtained an implementation through GSoC 2014. You can find it here. Its OpenCV tutorial is also present here.